Research On Identification Of Significant Edges For Complex Networks

From the view of essential elements of the complex network,the research of edges and nodes developed in 1980 s at the same time.The research of edges is still relatively less,although many scholars have proposed different methods to measure edge strength.As to the importance of nodes and edges,node importance has become mature,while the edge strength can't be regarded as its importance directly: in some cases,strong edges are not always important and weak edges are not necessarily unimportant.Moreover,in case of weighted networks,the weight of an edge can't be regarded as edge significance directly,it can only be a reference of measuring the importance.Therefore,in different applications,how to quantify the edge importance is particularly critical.Edge plays the connection role in complex networks,and the number of edges in a network is much larger than that of nodes.Compared with the nodes,impact of the increase and deletion of the same number of edges on the existing statistical characteristics is relatively small,while in some aspects,some edges are very important.Hence,how to quantify edges is attached with great significance and its difficult is no less than measuring the importance of nodes.In this paper,we have done some research on edge importance from two aspects as follows:(1)One of the most basic functions for edges in the network is to maintain the connectivity between nodes or node sets.In this paper,we mine and quantify edges significance on maintaining global connectivity from the community angel,which is helpful to community evolution and auxiliary connection system by increasing redundant edges.Therefore,the paper proposed a new algorithm named LE(Link Entropy): firstly,the method of nonnegative matrix factorization is used to obtain probability distribution of each node that belongs to different communities,secondly,the edge significance is quantified based on information entropy and cross entropy.Through observation and analysis of edge percolation and the transitions of the largest connected component,the largest component is able to emerge in a small threshold.In addition,random initialization in the process of nonnegative matrix factorization has little effect and the requirement of community number is quite easy to satisfy.(2)Edge is the carrier of information dissemination,and information flow load of edges in different locations varies.How to control the edge to curb the spread of rumors quickly and maximize public information wildly is worthy getting more attention.In the process of information flow,the amount of information received by the node is directly related to the amount of information of its edges.In the paper,we proposed an algorithm IFL(Information Flow of Link)based on the information flow to get the edge information load and take it as the value of significance on the information dissemination.The algorithm uses the Gauss-Seidel iterative method and the adaptive updating principle based on neighbor weights,which can obtain stable results in limited iteration times.Because of the lack of recognized metric for testing edge significance in the process of information dissemination,we take the way of comparing the rank of nodes indirectly: by comparing the difference between node order in the paper and the benchmark obtained by averaging 1000 times of infectious disease model(SIR)results to verify the feasibility of the algorithm,we indirectly proves the rationality of edge significance on the information dissemination process.Experiments show that the node rank,which results from information load of its links,is of high accuracy,so it is reasonable for allocating the information load to edges.In a word,the research of identifying significant edges from two aspects are studied in this paper.Experimental results show the effectiveness of the algorithms on real networks.The research will provide new ideas for identification,and have application values in some domains such as knowledge discovery and social computing.