The Link Prediction Problem in Social Networks

Link Prediction LUCAS DOHMEN, RWTH Aachen University Link Prediction is an important topic in social network analysis. This seminar paper provides an overview of existing algorithms, compares them and provides use cases. Categories and Subject Descriptors: H.2.8 [Information Systems]: Database Management—Database ap- plications General Terms: Algorithms, Theory Additional Key Words and Phrases: Link Mining, Link Prediction 1. THE LINK PREDICTION PROBLEM In a social network there can be many different kind of links or edges between the nodes. Those could for example be social contacts, hyper-references or phone-calls. When social networks are analyzed, there are certain information about the linkage between the nodes that are not known or not known at a given point of time: Link Prediction is the problem of detecting edges that either don’t yet exist at the given time t or exist, but have not been discovered or tracked. This seminar paper will provide an overview of important algorithms for that prob- lem, they will be presented and compared to each other. Furthermore the analyzed papers feature test runs on huge data sets that will be reviewed and compared. 1.1. Use Cases and Data Sets A solution for this problem can be used in a lot of different situations, for example to suggest friendships in a social network [Backstrom and Leskovec 2011]. It could be used to find anomalous links [Rattigan and Jensen 2005] in a network to refine link prediction or to find errors. Link Prediction was also used to predict forthcoming co- operations between researchers [Lichtenwalter et al. 2010] or uncover hidden connec- tions in malicious networks or experiments, where finding them would be complicated and/or expensive [Krebs 2001, ]. In [Kunegis and Lommatzsch 2009] it was used on citation graphs, trust networks, a social tagging network, subgraphs of the world wide web, the Esperanto Wikipedia and two (joke and movie) rating sites. In [Lichtenwalter et al. 2010] data of 712 million cellular phone calls and the stream of 19,464 multi- agent events were analyzed. The data from the scientific publication network CiteSeer featuring a browsable citation graph was used in [Popescul et al. 2003]. The used data contains 271,343 documents and 1,092,200 citations. The authors of [Backstrom and Leskovec 2011] ran their algorithm on synthetic data before running it on the arXiv co-authorship network and the Facebook online social network. Other test runs where made on the Question-Answer-Site Yahoo! Chiebukuro [Murata and Moriyasu 2007]. Most of the algorithms are proposed on unweighted and undirected graphs, but for example in [Kunegis and Lommatzsch 2009] there is a specific application to weighted graphs. In [Lichtenwalter et al. 2010] one of the analysis is on a weighted and directed network of phone calls. 1.2. Algorithm Classifications There are different algorithms to predict links. In The link prediction problem for social networks [Liben-Nowell and Kleinberg 2003] the authors suggest a classification that will be used here: We differentiate between algorithms that Supervisor: Manh Cuong Pham, RWTH Aachen University Seminar Paper “The Link Prediction Problem in Social Networks” by Lucas Dohmen, 2011. A:2 Lucas Dohmen (1) look at the node neighborhood (2) look at the paths between all nodes (3) are meta approaches In addition the categories Bayesian Probabilistic Models and Linear Algebraic Meth- ods proposed in A Survey of Link Prediction in Social Networks [Hasan and Zaki 2011] have been added. 1.3. Comparisons Because the data is easy to collect and includes a lot of information about the exact timing whilst having little peril to mingle nodes with each other, a lot of test runs are made on co-authorship networks. Because this paper should give a good overview of which algorithm is adequate in which situation, a lot of statistics on the performance are given. Not a single paper gave exact information on the length of the test runs, so little information can be provided about the time efficiency of the algorithms. A lot of infor- mation is provided on the accuracy of the algorithms. For that purpose the collected data was separated into two parts, where the first part was the training set and the second part was used to check the predicted data. Therefor a good conclusion about the efficiency of the algorithm could be made. It is important to emphasize that the results vary between different datasets. Most of the comparison data is taken from [Liben-Nowell and Kleinberg 2003]. The authors compared the bigger part of the algorithms that are introduced in this paper on five sections of the physics e-Print arXiv. The obtained data are significant, because they were run on a large network and the same dataset was used for the compared algorithms. The papers introduced feature test runs themselves for the most parts, which are presented in this paper when considered meaningful and/or not covered in an external analysis or comparison. Seminar Paper “The Link Prediction Problem in Social Networks” by Lucas Dohmen, 2011. Link Prediction A:3 2. NODE NEIGHBORHOOD The algorithms in the following paragraph are based on the node neighborhood mean- ing the nodes directly connected to the two given nodes. These measurements are by nature easier to calculate than measurements on the entire graph. In the following algorithms Γ stands for the node neighborhood of the graph meaning its direct neigh- bors. 2.1. Common Neighbors The Common Neighbors measurement calculates the intersection of the sets of neigh- bors to provide a measure for similarity to predict future linkage. It is calculated by determining the intersection of the node neighborhoods as follows: CN (x, y) := |Γ(x) ∩ Γ(y)| This measurement is based on the idea that two nodes a and b have an increased probability to connect if they have a shared neighbor c as [Newman 2001] pointed out. With a growing number of shared neighbors this probability grows even higher. 2.2. Jaccard’s coefficient Jaccards coefficient [Dunn and Everitt 2004, p.26] measures how many of the features (in our case: neighbors) are shared between two nodes commensurate to all features that either one of the nodes has. In other words: Jaccard’s coefficient is a normalized variation of Common Neighbors. This can be expressed in the following way: |Γ(x) ∩ Γ(y)| J(x, y) := |Γ(x) ∪ Γ(y)| This is the Common Neighbors measurement normalized by the union of the node neighborhoods. As pointed out in [Hasan and Zaki 2011, p248] and visible in the comparison table the measurement performs worse than Common Neighbors on the data collected in [Liben-Nowell and Kleinberg 2003]. 2.3. Adamic/Adar In [Adamic and Adar 2003] the authors introduce a measurement that compares how many attributes two nodes have in common. They rate items that are unique to a few users more heavily than items shared amongst a hugh group of users. Using arbitrary attributes prevents the algorithm to be general-purpose, but this measurement can easily be adjusted in the context of node neighborhood by looking at shared neighbors as an attribute [Liben-Nowell and Kleinberg 2003]. Therefore the sum over the shared neighbors’ inverse of the logarithms of their neighborhoods is proposed and defined as follows: 1 AA(x, y) := log |Γ(z)| z∈Γ(x)∩Γ(y) 2.4. Preferential Attachment Preferential Attachment is based on the hypothesis that a node x will get new neigh- bors faster than a node y given y has less neighbors than x. [Newman 2001] uses the number of current neighbors to calculate the likelihood of a new edge involving this node. The following formula expresses the likelihood of two nodes being connected by Seminar Paper “The Link Prediction Problem in Social Networks” by Lucas Dohmen, 2011. A:4 Lucas Dohmen an edge based on preferential attachment by multiplying the number of their neigh- bors: P A(x, y) := |Γ(x)| · |Γ(y)| In [Jeong et al. 2003] the authors arrive at the conclusion that the growth of neigh- bors follows a power-law and not a linear growth like it was proposed before. They present the following formula for Π(k) where k is the amount of neighbors: α ki Π(ki ) := α j kj The authors calculated the value for the exponent α in four different networks where the form for the equation was found suitable and the following values where calculated for α on networks with different numbers of nodes and links: Database Number of Nodes Number of Links Exponent α Citation 1736 83252 0.95 ± 0.1 Internet 12409 13445 1.05 Collaboration 209293 3534724 0.79 ± 0.1 Actor 392340 33646882 0.81 ± 0.