Research On Key Nodes And Communities Discovery Of Social Networks Based On Persistent Homology

With the rapid development of social media and information technology,a large number of online social network platforms have emerged,such as We Chat,Weibo,and QQ.It is of great significance to deeply study the key nodes in the network and the analysis problems of the social network such as the information transmission and the suppression of bad information.In recent years,many scholars have proposed key node measurement and community discovery methods,which provide good theoretical and model tools for a better understanding of network structure-function.Centrality measurement is a common measurement of key nodes in the network.Traditional node centrality measurement only focuses on single topological information and measures key nodes from different angles.At the same time,most of the current community discovery problems are limited to the study of network graph structure,which can be combined with the key node discovery problem.The theory of persistent homology in topology can reflect the high-dimensional topology structure of the network and extract topological invariants from the data.Therefore,this paper uses persistent homology to study the key nodes and communities of social networks.The main work of this paper is as follows:(1)Key Node Discovery Algorithm Based on Simplex Centrality(KDSC)is proposed.The common measures used to measure key nodes in a network are degree centrality and betweenness centrality.Still,the traditional centrality measures only consider the local structural attributes of nodes and ignore the influence of nodes on the global structure of the network.The simplex of persistent homology theory can be used to describe the structural characteristics of the network.Therefore,the importance of nodes is defined as the degree of their influence on the number of network simplex,so as to more accurately discover the key nodes that affect the topological connection in the network and measure their importance.Secondly,this paper compares simplex centrality with traditional indexes and mainstream key node discovery algorithms,and conducts validation experiments on multiple datasets.Using persistence diagrams and barcodes,the paper quantitatively describes the influence of key nodes on the overall topological features of the network.Experimental results show that the KDSC algorithm can measure the critical nodes in the network accurately and effectively.(2)Metric Algorithm of Community Division Performance based on Persistent Homology(MCPH)is proposed.Community discovery is of great significance to studying the relationship between nodes in the network,and how to divide the community reasonably has always been an important problem.At present,there are few indexes to measure community division using topological structure characteristics.Therefore,from the perspective of network topological structure,this paper proposes a more comprehensive index of community division.Persistent homology can describe the result of community division from the different dimensions of sustainable characteristics,and use persistent homology to calculate the proportion of high-dimensional and lowdimensional characteristics after community division to measure the advantages and disadvantages of community division.An index is proposed to measure community division based on persistent homology,and the community’s structural characteristics are quantified using a persistence diagram and barcode.Finally,the classical community discovery datasets are used for experiments.The experimental results show that the MCPH algorithm can better reflect the changes in network topological characteristics after community division,and provide new ideas for community division measurement.(3)Block Division Algorithm based on Persistent Homology(BDPH)is proposed.On the basis of mining network key nodes with simplex numbers in the previous part,the method of network block division is proposed.Firstly,the key nodes of the network are mined with simplex centrality,and the initial block of the network is extended according to the neighbor nodes,and the remaining nodes are divided into the initial block by using the simplex contribution rate of the nodes.Finally,the block division is realized.From the real datasets experiment,the BDPH algorithm can reasonably partition blocks.