Research On Community Evolution And Link Prediction In Dynamic Social Networks Based On The Attraction Force Between Nodes

With the rapid development of Internet technology and communication technology at present,the emergence of online social networks led by We Chat,Twitter,Taobao and Facebook has greatly enriched and facilitated people's daily life,and also has broken through the traditional geographical restrictions,so that people all over the world can participate in the global social networks.With the increasing number of people participate in social networks,social networks have developed from the traditional human-centered networks to complex large-scale networks in multi-level,sequence and heterogeneity,and the amount of data and information in the current social networks are unprecedented.Therefore,the analysis and research on social networks,especially on large-scale social networks with new features,have become important challenges for researchers.At present,more and more researchers are paying attention to the related research fields of social network analysis,such as community detection and link prediction,and many models and algorithms have been proposed successively.However,most of them are only targeted at specific aspects and have poor cross-domain adaptability.In order to solve the compatibility problem among multiple fields of social network,the whole network is modeled in the beginning of this dissertation.It is assumed the attraction force exists between different nodes in a network and each node is endowed with mass.The attraction force between nodes can be measured by introducing the law of universal gravitation,and corresponding levels can be assigned to each node according to its mass and links to other nodes.On the basis od these,the work in this dissertation focus on four aspects: community detection and connection strength measurement for link in static networks,community evolution in dynamic networks,potential link prediction and real link prediction in dynamic networks.The main research contents of this dissertation and the corresponding contributions are described as follows:(1)Community detection and connection strength measurement for links are researched in traditional static social networks without considering time change.On the one hand,a community detection algorithm in static networks based on the attraction force between nodes is proposed.As a connection-based clustering method,the algorithm first selects the nodes with local maximum characters from the global as the core of communities,other nodes can be divided into the corresponding communities depending on the attraction forces through multiple iterations,and the overlapping nodes can also be detected.On the other hand,an approach of connection strength measurement for links in static networks based on the attraction force between nodes is proposed,which can be used to measure the connection strength of links between any two nodes in a network according to the condition whether the nodes belong to the same community.The algorithm contains the connection strength measurement for real links and potential links between nodes.Finally,experiments are conducted on some real-world social networks to verify the effectiveness of the proposed community detection algorithm and the approach of connection strength measurement for links by comparing with some existing algorithms.(2)According to the proposed community detection algorithm in static networks,a community evolution model in dynamic networks based on the attraction force between nodes is proposed with considering time change.At first,the mass of each node is updated depending on the network changes over time,and the core nodes chain of each community is also dynamically adjusted depending on the changes of attraction forces.The evolutionary behaviors of communities over time can be modeled: a new community is formed when a new core nodes chain appeared;a community is died out when its core nodes chain disappeared;some communities are merged when their core nodes chains connected with each other;a community is split when its core nodes chain broke into several parts;a community is shrunk or expanded when its core nodes chain kept stable but some nodes added to or quit from the community.Finally,experiment on some real-world social networks to validate the validity of the proposed community evolution model and verify the proposed model can identify the major six community evolutionary behaviors by comparing with some comparison algorithms.(3)On the basis of the proposed approach of connection strength measurement for links in static networks,a potential link prediction algorithm in dynamic networks based on the attraction force between nodes and node level assignment is proposed.At first,the network structure is updated and a virtual snapshot between two adjacent snapshots is built depending on the network “surface” changes over time,the connection probability of each potential link can be calculated by comparing the level difference of nodes connected to the link.The greater connection probability of a potential link means the higher possibility that the potential link would become a real link.All the potential links in the network can be sorted according to their connection probability.Finally,experiments are conducted on some real-world social networks to verify the accuracy and effectiveness of the proposed potential link prediction algorithm by comparing with some existing algorithms.(4)In addition to predicting potential links in dynamic networks,a real link prediction algorithm in dynamic networks based on the attraction force between nodes and node level assignment is also proposed.Similar to the proposed potential link prediction algorithm,the network structure is updated and a virtual snapshot between two adjacent snapshots is built at first depending on the network “surface” changes over time,the rupture probability of each real link can be calculated by comparing the level difference of nodes connected to the link.As the connection probability of potential links,the greater rupture probability of a real link means the higher possibility that the real link would break.All the real links in the network can be sorted according to their rupture probability.Finally,some experiments are conducted on some realworld social networks to verify the accuracy and effectiveness of the proposed real link prediction algorithm by comparing with some other algorithms.