Decay centrality in social graphs and Flajolet-Martin algorithm adaptation for its computation

Boris Toropov


The paper is devoted to a node centrality in a graph, which is a generalization of degree and closeness centralities for social graphs. This centrality form is based on a power function, known as decay centrality and proposed by Jackson and Wolinsky. Author examines Flajolet-Martin adopted algorithm for decay centrality approximation. The results are compared to the real closeness centrality values. Computational experiment has shown, that centrality form exposed along with the algorithm adopted for its computation are suited for social network graphs closeness centrality approximation. Research methodology is based on elements of graph theory and social network analysis. 

Full Text:

PDF (Russian)


Freeman L.C. Centrality in social networks: Conceptual clarification // Social Networks. 1978. №1. P. 215-239

Tsvetovat M. Kouznetsov A. Social Network Analysis for Startups. O’Reilly Media Inc., 2011. 192 p.

Banerjee A., Chandrasekhar A.G., Duflo E., Jackson M.O. The Diffusion of Microfinance // Science. 2013. №. 341 P. 363-340 DOI:10.1126/science.1236498

Kang U., Papadimitriou S., Sun J., Tong H. Centralities in Large Networks: Algorithms and Observations // Proceedings of the 2011 SIAM International Conference on Data Mining. 2011. P. 119-130

Johnson D. B. Efficient algorithms for shortest paths in sparse networks // Journal of the ACM. 1977. V.24. №1. P. 1-13

Zhao J., John C.S. Lui, Towsley D., Guan X.H. Measuring and Maximizing Group Closeness Centrality over Disk-Resident Graphs // Proceedings of the 23rd International Conference on World Wide Web. Republic and Canton of Geneva, Switzerland. 2014. P. 689–694

Jackson M.O., Wolinsky A. A Strategic Model of Social and Economic Networks // Journal of Economic Theory. 1996. V. 71. №1 P. 44 – 74

Jackson M.O. Social and Economic Networks. Princeton University Press, 2008. 520 p.

Milgram S. The Small‐World Problem // Psychology Today. 1967. №1. P. 60–67

Adamic L.A. The SmallWorldWeb // Proceedings of the International Conference on Theory and Practice of Digital Libraries. Springer Berlin Heidelberg. 1999. P. 443-452

Cannarella J., Spechler J.A. Epidemiological modeling of online social network dynamics. 2014. Cornell University Library.

Backstrom, L., P. Boldiy, M. Rosay, .J. Ugander S. Vignay. Four Degrees of Separation. 2012. Cornell University Library.

Catanese S., De Meo P., Ferrara E., Fiumara G. Analyzing the Facebook friendship graph // CEUR Workshop Proceedings. 2010. P.14-19

Flajolet P., Martin G.N. Probabilistic counting algorithms for data base applications // Journal of Computer and System Sciences. 1985. V.31. №2. P. 182–209

Palmer C.R., Gibbons P.B., Faloutsos C. ANF: A Fast and Scalable Tool for Data Mining in Massive Graphs // Proceedings of the Eighth ACM SIGKDD international Conference on Knowledge Discovery and Data Mining. 2002. P. 81-90

Erdos P., Renyi A. On Random Graphs. I. // Publicationes Mathematicae. 1959. V.6. P.290–297

McAuley J., Leskovec J. Learning to Discover Social Circles in Ego Networks // Proceedings of the Advances in Neural Information Processing Systems 25. 2012. PP. 548–556


  • There are currently no refbacks.

IT-EDU-2017   RTUWO 2017

ISSN: 2307-8162