Research On Community Discovery And Link Prediction In Weighted Networks

With the rapid development and popularization of micro-blog,forums,instant messaging and other social network applications,the social network has become an indispensable part of people's lives.As a result,the analysis and research on social networks have become the focus of our attention.Among them,discovering the community structure of the network and predicting links in the network evolution are very important.By studying the structural characteristics and behavior pattern of the real network,we can find its potential evolution law and predict the network behavior,which will help to explain social phenomena,such as propagation and stimulation of network information,situation analysis of users.In this paper,we focus on the community discovery and link prediction in weighted social networks.The main content is as follows.Firstly,to improve the present AGMA algorithm,the CRMA algorithm based on the connection strength is proposed for community discovery in weighted networks.The algorithm consists of three stages,namely,clustering,reclustering and merging.In the first two stages,in order to solve the problem that some nodes can not be reasonably clustered by AGMA algorithm,the joint degree between the node and the community is defined based on the network topology characteristics such as the strength of the node and the sign of the edge.On this basis,all nodes are reasonably clustered according to the friend coefficient between the node and the community,and the clustering situation of neighbor nodes of the current node.Then the initial communities are discovered.In the third stage,in order to solve the problem that the network modularity is low in terms of community division results of AGMA algorithm in certain unweighted networks,the density of the community and the joint strength between communities are defined.When they satisfy certain relation,the two corresponding communities would be merged so as to optimize the initial division result and then the ultimate community structure can be discovered.Secondly,aiming at the deficiency of existing weighted similarity indexes,the IEM algorithm is proposed based on the similarity of common neighbors so as to achieve a more reasonable division of weighted networks.The algorithm consists of three stages,namely,forming the initial community,expanding communities and merging them.In the first two stages,we focus on the influence of common neighbors to the similarity of the two nodes.The effect coefficient and joint strength of the common neighbor are defined firstly.In the case of the two nodes having no common neighbors,the edge weight strength is defined as their similarity.After that the weighted similarity of the two nodes based on their common neighbors is defined.Then the most closely related nodes are clustered fastly according to their similarity to form the initial community and expand it.In the third stage,for those small communities consisting of only two nodes that may emerge in the first two stages,they would be merged by maximizing the weighted modularity of the network,thus the more reason and accurate community division result could be got.Thirdly,mainstream link prediction algorithms based on the similarity only consider the influence of attributes of the node or the path structure to the similarity,which leads to the imbalance between prediction accuracy and computational complexity.And these algorithms can not be directly applied to the signed network.Therefore,a new algorithm STNMP based on the similarity of transmission nodes of multipath is proposed for link prediction in weighted networks.On the basis of the static snapshot of the weighted network,the edge weight strength of the node pair is defined to measure the local similarity of the two nodes.And the path similarity contribution is also defined to measure the path structure similarity between the two nodes.After that,the similarity based on the transmission nodes of multipath is defined as the total similarity of the two nodes through effective fusion of local similarity and path structure similarity.In the following experiments,in order to achieve a higher accuracy and reduce the complexity simultanously,the optimal step size is determined by the adjustment of the parameter.Finally,in view of the problem that existing sign prediction algorithms can only predict the sign of existing edges without achieving the prediction of future links,a new algorithm PSN_BS is proposed based on the similarity and the structural balance theroy in order to achieve link and sign prediction simultaneously in the signed network.Based on the paths connecting the two nodes with the step size of 2 and 3,the prediction score of the two nodes based on the structural balance theory is defined through effective fusion of local similarity and path structure similarity on the basis of introducing the step size influence factor.Concerning the uncertainty of the sign when the prediction score is 0,the concept of negative density of the node is introduced so as to predict the sign using the degree information of the node.Then link and sign prediction are completed according to the prediction score of the two nodes and their negative density.The correctness and effectiveness of the above algorithms proposed are verified through experiments.