Community Detection And Link Prediction Of Complex Network

Community structure is one of the most important features of complex network,which can be used to express some functions and features of the network.Link prediction uses known network topology features and node attributes to predict the probability of a link between two nodes.Both of them have great practical significance for the application and research of complex systems in real life.In order to reduce the instability of clustering results caused by randomness in association discovery,the community belonging degree is used to determine the number of community and the initial shape of the community,to improve the random selection defect of the label propagation algorithm.The proposed LPA-CBD(Label Propagation Algorithm Based on Community Belonging Degree)first searches for the initial community of the maximum attraction nodes,and then optimizes or expands the initial community according to the degree of community ownership.After getting the initial community division,tag selection is used for residual nodes using label propagation algorithm.The experiment is tested on ten real networks and three artificial networks,and compared with the classical LPA,random walk algorithm,BGLL,GN,fast greedy,and Leading Eigenvector algorithms.The evaluation indexes are the CN(Community Number),Accuracy and Modularity.The experimental results prove that the LPA-CBD performs well on each index.LPA-CBD not only has low algorithm complexity and high quality of community discovery,but also improves the stability of the original label propagation algorithm.Community structure is one of the most common topological features in the network.The community structure of real networks not only hierarchical,but also overlapping.At present,most work only studies one side of these two properties of the network.The article published in 2010 by Ahn etc.al proves that hierarchy and overlap are two aspects of the same phenomenon of the network community structure.In this manuscript,a new algorithm for community detection is proposed: SAoLG(Spectral Analsis of Line Graph).SAoLG applies spectral analysis to the edge community detection.In this study,a hierarchical and overlapping community detection study was carried out.The networks used in the experiment are a standard network,two networks with clear structure(Karate club network and Dolphin social network)and four other real networks.The evaluation criteria of the experimental results are Modularity,PD(Partition Density),CN(Community Number),CR(Coverage Rate of vertices),UV(Uncovered Vertices),Accuracy,and CDV(Correctly Divided Vertices).The experimental results show that the SAoLG algorithm achieves the detection of overlapping communities and the result of community partition is better than the other three classical community detection algorithms.The community structure of network also affects the accuracy of link prediction in complex networks.The use of the feature vectors of the Laplacian matrix of the graph as the sample space to divide the community structure can converge to the global optimal.It is one of the best methods to divide the community structure.By introducing the similarity calculation method based on Laplacian matrix,a new link prediction algorithm named LPbSA(Link Prediction based on Spectral Analysis)is proposed.The LPbSA extracts attributes directly from edges and predicts edges based on their attribute values.The LPbSA algorithm first obtains the eigenvalues and eigenvectors of the network’s Laplacian matrix;then it selects the dimension of the minimum nontrivial eigenvector to be 2 and 3 dimensions,obtaining the similarity between the 2 and the 3 eigenvectors respectively are obtained(three similarities are the Angle distance,the Euclidean distance and the Manhattan distance).There are 6 attributes of the possible edge of the node pair between all nodes,and then use machine learning algorithm to classify the edges.The values of the classified variables are 0 and 1,of which 0 indicate that the node pairs are not connected,and the 1 indicates the connection between the nodes.Thus the link prediction problem of the network is changed into the classification prediction problem The experiment is tested on seven real data sets,and compared with the eighteen similarity indexes.The experimental results prove the feasibility and effectiveness of the LPbSA algorithm.