Despite there being relatively frequent discourse regarding the usage and effectiveness of various node centralities when analysing the influential spreaders of a graph, I have thus far struggled to find any formal treatments of such discussions. For example, betweeness centrality is theoretically well-defined and is popular in practice for finding influential spreading members, but is there any proof of its effectiveness in this capacity (e.g. compared to any other centrality)? All the arguments I have witnessed thus far have been largely simulation/virtual-experiment based. My question is: is there anywhere I can more formal treatments of this subject matter?

Whilst I am generally curious to see if possible formal discussions around graph analysis efficacy could exist, I have my suspicions as to why this is not already the case given that formal comparisons of this nature could be infeasible... but perhaps this is not true?

Example papers/articles: https://www.nature.com/articles/nphys1746.pdf https://www.nature.com/articles/srep19307.pdf https://cambridge-intelligence.com/keylines-faqs-social-network-analysis/

  • $\begingroup$ Don't expect any kind of formal mathematics in Nature. $\endgroup$ – David Richerby Nov 30 '18 at 13:51
  • $\begingroup$ Thank you for the tip! Do you know of anywhere I would be likely to find formal mathematics on these areas? $\endgroup$ – Sean Frötkék Nov 30 '18 at 14:15
  • $\begingroup$ Probably the best way is to start looking at papers that cite and are cited by the papers you already know, prioritizing the ones in good maths/CS journals or good CS conferences. Having said that, it's not clear that what you want exists. The centrality measures of course have formal definitions, but the concepts they're supposed to represent seem rather fuzzy. $\endgroup$ – David Richerby Nov 30 '18 at 14:55
  • $\begingroup$ I agree completely. I confess I don't think that such formal proofs exist because there isn't any clear condition or statement for them to actually be proving... $\endgroup$ – Sean Frötkék Nov 30 '18 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.