Eng During last 365 days Approved articles: 1936,   Articles in work: 286 Declined articles: 829 
Articles and journals | Tariffs | Payments | Your profile

Back to contents

Flajolet-Martin algorithm as an effective social network analysis tool.
Toropov Boris Andreevich

PhD in Technical Science

Associate Professor at the IT Department of the Academy of Management of the Ministry of Internal Affairs of the Russian Federation

125171, Russia, Moscow, ul. Z.i A. Kosmodem'yanskikh, 8





The study is devoted to the influence (centrality) model of a social network participant.  The object of studies involves calculations for the centrality metrics, which are based upon the shortest path lengths between the graph vertices for the social graph based upon the iterative performance of the Flajolet-Martin algorithm. The author evaluates the possibility of approximate evaluation of closeness-centrality based on a simple example. Then, having the calculation results, teh author compares the computed values with the real closeness values, as computed by breadth-first search algorithm (BFS-Algorithm). The methodology of the study involves graph theory elements, as well as the social network analysis apparatus, which allows to compute different centrality metrics of a graph vertex. The key conclusion provides that the Flajolet-Martin algorithm is an easily adaptable tool for the approximate social graph vertex centrality evaluation related with the shortest paths, such as closeness or centrality of the disintegration, as provided for in the work so M. Jackson. In turn, it provides for the new possibilities for the process modeling for the spread of information in the social networks.

Keywords: approximation, code sequence, Flajolet-Martin algorithm, shortest path, closeness, centrality, social graph, social network, computational complexity, social network analysis



Article was received:


Review date:


Publish date:


This article written in Russian. You can find full text of article in Russian here .

U. Kang, Spiros Papadimitriou, Jimeng Sun, Hanghang Tong. Centralities in Large Networks: Algorithms and Observations. Proceedings of the 2011 SIAM International Conference on Data Mining, 2011, pp. 119-130.
P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31, 1985, pp. 182209.
Christopher R. Palmer, Phillip B. Gibbons, Christos Faloutsos. 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, pp. 81-90.
Matthew O. Jackson. Social and Economic Networks. Princeton University Press. 2008. 520 p.