Actual Paper: http://www.cs.utexas.edu/~yzhang/papers/osn-imc09.pdf
Estimating proximity between nodes in social networks is challenging due to size and dynamic nature of networks. Proximity measure is the central measure in analysis of social networks. Proximity sketching and Proximity embedding are proposed in this paper. They are demonstrated using Link Prediction problem on multiple networks.
Simplest proximity estimations are based on the information flow between the nodes, between neighbors of nodes. Katz Measure, Rooted Page Rank and Escape probability are used in this paper.
We’ve studied more on link prediction part of this paper as we are interested solving this problem for the purpose of our project.
1. Basic Link Predictors: Link exists between a pair of nodes, if the similarity between the nodes crosses certain threshold value.
2. Composite Link Predictors: can be applied through Weka, using multiple predictors.
Proximity Measures:
Graph Based:
1. Shorted path distance between pair of nodes in existing graph.
2. Dijkstra is inefficient for graphs with large no. of nodes. In this paper, they applied expanded ring search.
Node neighbourhood based:
1. No of common neighbours.
2. More weight to common neighbors with small no. of friends.
3. Preferential attachment: Product of neighbours of both nodes.
4. PageRank: The PageRank of a node depends on the count of inbound links and the PageRank of outbound neighbors
5. Path ensemble based – Eg: Katz Measure.
For link prediction, they have divided data sets into three parts over time lines S1, S2, S3. Based on information from S1 and S2, they will predict links that will be formed in S3.
In the friendship link prediction problem, we construct the positive set as the set of user pairs that were not friends in the first snapshot, but become friends in the second snapshot. The negative set consists of user pairs that are friends in neither snapshots.
Accuracy is measured interms of FP and FN.
FN = #of missed friend links / #of new-friend links
FP = #of incorrectly predicted friend links / #of non-friend links
Computational time for each proximity for a single pair of a nodes is shown in results.
Related work on Social Networks, Proximity Measures, Link Prediction, Dimensionality Reduction is studied.
Leave a Reply