Dynamic Link Prediction Based On Motif Evolution In Social Networks

The research of complex network has great practical significance,which can help us understand the evolution of networks formed by various complex systems such as social networks,biological networks,transportation networks and so on.Link prediction is a research field that crosses the complex network and data mining which mainly studies the possibility of connecting nodes in complex networks.Link prediction has important value for the evolution of the complex network research,which also has the application value in friend recommendation and studies on protein interaction networks.At present,the time evolution information of the network is seldom used in the research of link prediction,which is always aimed at the undirected network.And little attention has been paid to the evolution of the microstructure of the network.However,most of the networks are directed and evolution over time in reality.Therefore,this thesis focuses on link prediction researches for the most common and accessible dynamic social networks in life.The concept of motif comes from the biological field originally and represents the basic functional substructure in the network.we can study the triad motif of the smallest functional substructure in a complex network and apply this into link prediction.In addition,complex networks,especially social networks,mostly have a community structure,which is naturally formed in a long period of evolution.In the network,the nodes in the same community are more closely connected,and the nodes in different communities are sparsely connected.In order to solve these problems,the following works are done in this thesis: Firstly,a link prediction method in a directed dynamic social network is proposed.This method concentrates on the dynamic evolution of the triad motif.It divides the dynamic network according to a certain time span slice.Then it counts the transition probabilities of the triad motif among adjacent time slices,analyzes the transitional probabilities of the motif to obtain a time-series analysis,and gets a triad transition probability prediction matrix.Then it can be used for link prediction.Through experimental comparison,it is found that this algorithm can obtain better results than Common Neighbor,Triad Transition Matrix and other methods.Secondly,the analysis of the experimental results are given and it is found that the proposed method has the best effect in the network with high global clustering coefficient and high average degree.Thirdly an hypothesis based on the community structure of social networks is put forward,which is that the triple motif contributes the more possibility for edges' connecting if three nodes in a triple motif belongs to the same community and vice versa.Based on this hypothesis,an improved algorithm is proposed.Its principle is to define the community consistency degree of the triad motif and use it to calculate the edge score.Experimental results show that the improved algorithm has better results than the above proposed algorithm.