Temporal Link Prediction And Local Community Detection For Complex Networks

Complex Network is an effective way to describe complex systems.For example,biological systems,social systems,transportation systems,power systems and so on.Link Prediction and Community Detection are the main methods for analyzing the regularities and characteristics of complex networks.Link Prediction refers to the process of predicting the potential or future links based on the existing network links,it can be used to reveal the peer-to-peer similarity between objects in the network system;according to the network topology or nodes’ attribute information,community detection divides nodes into different communities,community detection is essentially the clustering process of objects in complex systems..Based on the local structure information,this thesis will analyze and research temporal link prediction,local community detection and their distribution in complex networks,including the following aspects:(1)Aiming at the low accuracy of the current link prediction algorithm,a link prediction algorithm based on time series information is proposed in this thesis.Firstly,the link frequency between nodes at different times is compressed into the weighted link between nodes,and then the improved label propagation algorithm is used to predict the future links based on the compressed graph.In the process of label propagation,the compressed weight of links are used to correct the similar information in the label,and finally each node aggregates received similar information as the final link score,a score threshold can be used to determine the predicted links.(2)In view of the low efficiency of current community detection algorithms,a local community detection algorithm based on local information is proposed in this thesis.In order to solve the problem that the local community detection algorithm is sensitive to the position of the initial election points,firstly,the relationship density of each node is calculated based on the degree of nodes and the adjoining edges of the nodes’ neighbors.Then,based on Gaussian blurring algorithm,the node’s own relationship density and its neighbors’ are used to calculate the community centrality of each node.From the given initial seed node,the community centrality of nodes are used to guide random walk and find the local community center near the seed nodes.Finally,starting from the found local community center nodes,it expands outwards and continuously brings the nodes around the local community into the community under the premise of increasing the cohesion coefficient.After the iterations,the local communities which sed nodes belongs to are detected more accurately.(3)Currently,the scale of complex networks grows rapidly.In order to meet the demand of analyzing large-scale complex networks,distribution and parallelization of temporal link prediction and local community detection algorithms is implemented respectively based on Spark GraphX,a distributed computing framework.