Social Networks Analysis Using Similarity-Based Metrics

Real-life networks are agile in nature, fresh vertices and edges are added over the passage of time.

It is very important to know the possibility of new link creation.

The basic idea of link prediction is to approximate the possibility of the existence of a link between pair of nodes, derive from perceived topological structural attributes of nodes.

Motivation

Link prediction methods have a variety of uses in diverse areas.

a) Online Social Networks

b) Recommender System

c) Health Care

BenchMark Algorithms

a) Common Neighbor

The ranking of the likelihood of edges is based on the number of common neighbors between two distinct nodes.

b) Common Neighbor & Distance

When there are no common neighbors between them Γ(i)∩Γ(j)=Ø, distance d between nodes is used for score.

c) Preferential Attachment

The ranking of scores is based on the degree multiplication of two distinct nodes.

d) Resource Allocation

The similarity index is defined as the amount of resource node i receives from node j through indirect links and each intermediate link contributes a unit of resource.

e) Adamic Adar

Improves the scoring by weighting lesser degree nodes heavily.

f) Jaccard Index

Is the ratio of common neighbors to that of all neighbors.

g) Soreson Index

Is the ratio of common neighbor to that of their submission of their degrees.

h) Hub Promoted Index

The score is computed by computing the Ratio of common neighbors to that of the minimum degree of connected nodes.

i) Common Neighbor and Centrality based Patameterizzed Algorithm (CCPA)

Common neighbor and degree centrality are combined in a parameterized manner to compute the score for a missing link in the graph.
By configuring 𝛼=0.1 the algorithm is assigning 10% weightage to common neighbors and 90% weightage to the centrality of a node.

Takeaway

Different structural based similarity algorithms may perform differently on a variety of datasets.

References

1. Gupta, P., Goel, A., Lin, J., Sharma, A., Wang, D., & Zadeh, R. (2013, May). Wtf: The who to follow service at twitter. In Proceedings of the 22nd international conference on World Wide Web (pp. 505–514). ACM.
2. 1.He, Y. L., Liu, J. N., Hu, Y. X., & Wang, X. Z. (2015). OWA operator based link prediction ensemble for social network. Expert Systems with Applications, 42(1), 21–50.
3. 1.Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., & Arenas, A. (2003). Self-similar community structure in a network of human interactions. Physical review E, 68(6), 065103.
4. 1.Yang, Y., Chawla, N. V., Basu, P., Prabhala, B., & La Porta, T. (2013, August). Link prediction in human mobility networks. In Advances in Social Networks Analysis and Mining (ASONAM), 2013 IEEE/ACM International Conference on (pp. 380–387). IEEE.
5. 1.Yang, J., & Zhang, X. D. (2016). Predicting missing links in complex networks based on common neighbors and distance. Scientific reports, 6, 38208.
6. 1.Liben‐Nowell, D., & Kleinberg, J. (2007). The link‐prediction problem for social networks. Journal of the American society for information science and technology, 58(7), 1019–1031.
7. 1.Lü, L., Jin, C. H., & Zhou, T. (2009). Similarity index based on local paths for link prediction of complex networks. Physical Review E, 80(4), 046122.
8. 1.Gao, F., Musial, K., Cooper, C., & Tsoka, S. (2015). Link prediction methods and their accuracy for different social networks and network metrics. Scientific programming, 2015, 1.
9. 1.Silva, T. C., & Zhao, L. (2012). Semi-supervised learning guided by the modularity measure in complex networks. Neurocomputing, 78(1), 30–37.
10. 1.Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003). The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 54(4), 396–405.
11. 1.Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’networks. nature, 393(6684), 440.