2
$\begingroup$

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/

Improve this question
$\endgroup$
4
  • $\begingroup$ Don't expect any kind of formal mathematics in Nature. $\endgroup$
    – David Richerby
    Nov 30, 2018 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 S
    Nov 30, 2018 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, 2018 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 S
    Nov 30, 2018 at 15:06

1 Answer 1

Reset to default
2
$\begingroup$

There are many papers dealing with the algorithmic aspects of these measures, with formal proofs, complexity analysis, and so on. However, I understand that this is not really what you are looking for.

There are only few formal works on their actual relevance for describing features of interest in practice.

Pagerank is a notable exception, though. Its connections to random walks, Markov chains, and matrices, as well as its wide use and mere features, make it a great metric for formal analysis. I particularly recommend the book Google's PageRank and Beyond: The Science of Search Engine Rankings, by Amy N. Langville and Carl D. Meyer. It deals with many aspects, putting together practical concerns as well as theoretical analysis.

Node degree distribution is another important exception, although one may consider it too basic to be a valid answer here. Still, there are many formal works showing the importance of high degree nodes in random graphs that model real-world complex networks. See for instance our survey entitled Impact of random failures and attacks on Poisson and power-law random networks.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for such a detailed answer! In the time since I posted this question I have come to agree with your answer and so am marking it as correct. Clearly, formalizing the intuitions behind such properties is an active area of research. Indeed, random walks seem to be a crucial component of such works! $\endgroup$
    – Sean S
    Jan 3, 2021 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.