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
Abstract. 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.
approximation, code sequence, Flajolet-Martin algorithm, shortest path, closeness, centrality, social graph, social network, computational complexity, social network analysis
Article was received: 16-03-2017
This article written in Russian. You can find full text of article in Russian here.