Uncovering factors underlying the network formation is a long-standing challenge for data mining and network analysis. In particular, the microscopic organizing principles of directed networks are less understood than those of undirected networks. This article proposes a hypothesis named potential theory, which assumes that every directed link corresponds to a decrease of a unit potential and subgraphs with definable potential values for all nodes are preferred. Combining the potential theory with the clustering and homophily mechanisms, it is deduced that the Bi-fan structure consisting of 4 nodes and 4 directed links is the most favored local structure in directed networks. Our hypothesis receives strongly positive supports from extensive experiments on 15 directed networks drawn from disparate fields, as indicated by the most accurate and robust performance of Bi-fan predictor within the link prediction framework. In summary, our main contribution is twofold: (i) We propose a new mechanism for the local organization of directed networks; (ii) We design the corresponding link prediction algorithm, which can not only testify our hypothesis, but also find out direct applications in missing link prediction and friendship recommendation.
Link prediction is one of the most fundamental problems in networked data mining that attempts to estimate the likelihood of the existence of a link between two nodes, according to observed links and the attributes of nodes @cite_21 @cite_41 . It has found applications in predicting missing links of biological networks and recommending social mates in online social networks. To evaluate the algorithmic performance, we usually divide the data into two parts and use the training set to predict the testing set. The algorithmic accuracy is quantified by counting the overlap of prediction and the testing set and or the ranks of links in the testing set among all non-observed links (i.e., node pairs not in the training set). Link prediction algorithm can be used in judging the driven mechanisms of network formation. The very nice performance of common-neighbor-based similarity indices strongly supports the validity of clustering mechanism @cite_31 @cite_37 . On several real friendship networks, @cite_25 showed that when combined with topological features, topical similarity achieves a link prediction accuracy of about 92
@cite_37 @cite_41 @cite_21 @cite_31 @cite_25
2007444087 2032553509 1996564243 2136116685
Missing link prediction in networks is of both theoretical interest and practical significance in modern science. In this paper, we empirically investigate a simple framework of link prediction on the basis of node similarity. We compare nine well-known local similarity measures on six real networks. The results indicate that the simplest measure, namely Common Neighbours, has the best overall performance, and the Adamic-Adar index performs second best. A new similarity measure, motivated by the resource allocation process taking place on networks, is proposed and shown to have higher prediction accuracy than common neighbours. It is found that many links are assigned the same scores if only the information of the nearest neighbours is used. We therefore design another new measure exploiting information on the next nearest neighbours, which can remarkably enhance the prediction accuracy. Link prediction is a task in Social Network Analysis that consists of predicting connections that are most likely to appear considering previous observed links in a social network. The majority of works in this area only performs the task by exploring the state of the network at a specific moment to make the prediction of new links, without considering the behavior of links as time goes by. In this light, we investigate if temporal information can bring any performance gain to the link prediction task. A traditional approach for link prediction uses a chosen topological similarity metric on non-connected pairs of nodes of the network at present time to obtain a score that is going to be used by an unsupervised or a supervised method for link prediction. Our approach initially consists of building time series for each pair of non-connected nodes by computing their similarity scores at different past times. Then, we deploy a forecasting model on these time series and use their forecasts as the final scores of the pairs. Our preliminary results using two link prediction methods (unsupervised and supervised) on co-authorship networks revealed satisfactory results when temporal information was considered. Prediction is one of the most attractive aspects in data mining. Link prediction has recently attracted the attention of many researchers as an effective technique to be used in graph based models in general and in particular for social network analysis due to the recent popularity of the field. Link prediction helps to understand associations between nodes in social communities. Existing link prediction-related approaches described in the literature are limited to predict links that are anticipated to exist in the future. To the best of our knowledge, none of the previous works in this area has explored the prediction of links that could disappear in the future. We argue that the latter set of links are important to know about; they are at least equally important as and do complement the positive link prediction process in order to plan better for the future. In this paper, we propose a link prediction model which is capable of predicting both links that might exist and links that may disappear in the future. The model has been successfully applied in two different though very related domains, namely health care and gene expression networks. The former application concentrates on physicians and their interactions while the second application covers genes and their interactions. We have tested our model using different classifiers and the reported results are encouraging. Finally, we compare our approach with the internal links approach and we reached the conclusion that our approach performs very well in both bipartite and non-bipartite graphs. Link prediction is a fundamental problem in social network analysis. The key technique in unsupervised link prediction is to find an appropriate similarity measure between nodes of a network. A class of wildly used similarity measures are based on random walk on graph. The traditional random walk (TRW) considers the link structures by treating all nodes in a network equivalently, and ignores the centrality of nodes of a network. However, in many real networks, nodes of a network not only prefer to link to the similar node, but also prefer to link to the central nodes of the network. To address this issue, we use maximal entropy random walk (MERW) for link prediction, which incorporates the centrality of nodes of the network. First, we study certain important properties of MERW on graph @math by constructing an eigen-weighted graph G. We show that the transition matrix and stationary distribution of MERW on G are identical to the ones of TRW on G. Based on G, we further give the maximal entropy graph Laplacians, and show how to fast compute the hitting time and commute time of MERW. Second, we propose four new graph kernels and two similarity measures based on MERW for link prediction. Finally, to exhibit the power of MERW in link prediction, we compare 27 various link prediction methods over 3 synthetic and 8 real networks. The results show that our newly proposed MERW based methods outperform the state-of-the-art method on most datasets.