SpringerLink
Log in

Community-based link prediction

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

This work proposes a community-based link prediction approach for identifying missing links or the links that are likely to appear in near future. Earlier works on link prediction consider only connectivity pattern or node attributes. We incorporate the notion of community structure in link prediction. An algorithm is designed to account the influence of communities on link prediction. We have considered recently developed edge centrality measures to compute likelihood scores of missing links. The performance of proposed algorithm is analyzed in terms of three metrics and execution time on both real-world networks and synthetic networks, where ground truth communities are already defined. The time complexity of proposed algorithm is also analyzed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. The terms, non-existing link and non-observed link are used interchangeably throughout the paper.

References

  1. Aiello LM, Barrat A, Schifanella R, Cattuto C, Markines B, Menczer F (2012) Friendship prediction and homophily in social media. ACM Transactions on the Web (TWEB) 6(2):9

    Google Scholar 

  2. Airoldi EM, Blei DM, Fienberg SE, **ng EP, Jaakkola T (2006) Mixed membership stochastic block models for relational data with application to protein-protein interactions. In: Proceedings of the international biometrics society annual meeting, pp. 1–34

  3. Akcora CG, Carminati B, Ferrari E (2011) Network and profile based measures for user similarities on social networks. In: 2011 IEEE international conference on, Information reuse and integration (IRI), pp. 292–298. IEEE

  4. Akcora CG, Carminati B, Ferrari E (2013) User similarities on social networks. Social Network Analysis and Mining 3(3):475–495

    Article  Google Scholar 

  5. Al Hasan M, Chaoji V, Salem S, Zaki M (2006) Link prediction using supervised learning. In: SDM06: Workshop on link analysis, counter-terrorism and security

  6. Al Hasan M, Zaki MJ (2011) A survey of link prediction in social networks. In: Social network data analytics, pp. 243–275. Springer

  7. Alahakoon T, Tripathi R, Kourtellis N, Simha R, Iamnitchi A (2011) K-path centrality: a new centrality measure in social networks. In: Proceedings of the 4th workshop on social network systems, p. 1. ACM

  8. Almansoori W, Gao S, Jarada TN, Elsheikh AM, Murshed AN, Jida J, Alhajj R, Rokne J (2012) Link prediction and classification in social networks and its application in healthcare and systems biology. Network Modeling Analysis in Health Informatics and Bioinformatics 1(1-2):27–36

    Article  Google Scholar 

  9. Anderson A, Huttenlocher D, Kleinberg J, Leskovec J (2012) Effects of user similarity in social media. In: Proceedings of the fifth ACM international conference on web search and data mining, pp. 703–712. ACM

  10. Backstrom L, Leskovec J (2011) Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the fourth ACM international conference on web search and data mining, pp. 635–644. ACM

  11. Bhattacharyya P, Garg A, Wu SF (2011) Analysis of user keyword similarity in online social networks. Social network analysis and mining 1(3):143–158

    Article  Google Scholar 

  12. Brandes U (2001) A faster algorithm for betweenness centrality*. Journal of mathematical sociology 25(2):163–177

    Article  MATH  Google Scholar 

  13. Bringmann B, Berlingerio M, Bonchi F, Gionis A (2010) Learning and predicting the evolution of social networks. IEEE Intelligent Systems 25(4):26–35

    Article  Google Scholar 

  14. Chen B, Chen L (2014) A link prediction algorithm based on ant colony optimization. Applied Intelligence 41(3):694–708

    Article  Google Scholar 

  15. Chen HH, Gou L, Zhang XL, Giles CL (2012) Discovering missing links in networks using vertex similarity measures. In: Proceedings of the 27th annual ACM symposium on applied computing, pp. 138–143. ACM

  16. Clauset A, Moore C, Newman ME (2008) Hierarchical structure and the prediction of missing links in networks. Nature 453(7191):98–101

    Article  Google Scholar 

  17. De Meo P, Ferrara E, Fiumara G, Ricciardello A (2012) A novel measure of edge centrality in social networks. Knowledge-based systems 30:136–150

    Article  Google Scholar 

  18. De Sá HR, Prudêncio RB (2011) Supervised link prediction in weighted networks. In: The 2011 International Joint Conference on, Neural networks (IJCNN), pp. 2281–2288. IEEE

  19. Ding J, Jiao L, Wu J, Hou Y, Qi Y (2015) Prediction of missing links based on multi-resolution community division. Physica A: Statistical Mechanics and its Applications 417:76–85. doi:10.1016/j.physa.2014.09.005

    Article  Google Scholar 

  20. Ding J, Jiao L, Wu J, Liu F (2016) Prediction of missing links based on community relevance and ruler inference. Knowledge-Based Systems 98:200–215. doi:10.1016/j.knosys.2016.01.034

    Article  Google Scholar 

  21. Fazel-Zarandi M, Devlin HJ, Huang Y, Contractor N (2011) Expert recommendation based on social drivers, social network analysis, and semantic data representation. In: Proceedings of the 2nd international workshop on information heterogeneity and fusion in recommender systems, pp. 41–48. ACM

  22. Fortunato S (2010) Community detection in graphs. Physics reports 486(3):75–174

    Article  MathSciNet  Google Scholar 

  23. Friedman N, Getoor L, Koller D, Pfeffer A (1999) Learning probabilistic relational models. In: IJCAI, vol. 99, pp. 1300–1309

  24. Geisser S (1993) Predictive inference: An introduction chapman & hall New York

  25. Girvan M, Newman ME (2002) Community structure in social and biological networks. Proceedings of the national academy of sciences 99(12):7821–7826

    Article  MathSciNet  MATH  Google Scholar 

  26. Guimerà R, Sales-Pardo M (2009) Missing and spurious interactions and the reconstruction of complex networks. Proceedings of the National Academy of Sciences 106(52):22,073–22,078

    Article  Google Scholar 

  27. Hanley JA, McNeil BJ (1982) The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology 143(1):29–36

    Article  Google Scholar 

  28. Hao W, Dongsu L (2015) Friend recommendation in social network. New Technology of Library and Information Service 1:012

    Google Scholar 

  29. Hayashi T, Akiba T, Yoshida Y (2016) Efficient algorithms for spanning tree centrality. In: Proceedings of the twenty-fifth international joint conference on artificial intelligence (IJCAI-16), pp. 3733– 3739

  30. Heckerman D, Meek C, Koller D (2004) Probabilistic entity-relationship models, PRMs, and plate models. In: Proceedings of the ICML-2004 Workshop on Statistical Relational Learning and its Connections to Other Fields. IMLS, Banff, Canada, pp 55–60

  31. Herlocker JL, Konstan JA, Terveen LG, Riedl JT (2004) Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems (TOIS) 22(1):5–53

    Article  Google Scholar 

  32. Huang Z, Lin DK (2009) The time-series link prediction problem with applications in communication surveillance. INFORMS Journal on Computing 21(2):286–303

    Article  Google Scholar 

  33. Jaccard P (1901) Etude comparative de la distribution florale dans une portion des Alpes et du Jura, vol. 37. Impr Corbaz

  34. Jeh G, Widom J (2002) Simrank: a measure of structural-context similarity. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining, pp. 538– 543. ACM

  35. Jeong H, Tombor B, Albert R, Oltvai ZN, Barabási AL (2000) The large-scale organization of metabolic networks. Nature 407(6804):651–654

    Article  Google Scholar 

  36. Juszczyszyn K, Musial K, Budka M (2011) Link prediction based on subgraph evolution in dynamic social networks. In: 2011 IEEE third international conference on, Privacy, security, risk and trust (PASSAT) and 2011 IEEE third inernational conference on social computing (socialcom), pp. 27–34. IEEE

  37. Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43

    Article  MATH  Google Scholar 

  38. Kim M, Leskovec J (2011) Modeling social networks with node attributes using the multiplicative attribute graph model. ar**v preprint ar**v:1106.5053

  39. Kim M, Leskovec J (2011) The network completion problem: Inferring missing nodes and edges in networks. In: SDM, vol. 11, pp. 47–58. SIAM

  40. Kiousis S, Popescu C, Mitrook M (2007) Understanding influence on corporate reputation: an examination of public relations efforts, media coverage, public opinion, and financial performance from an agenda-building and agenda-setting perspective. Journal of Public Relations Research 19(2):147– 165

    Article  Google Scholar 

  41. Kuang R, Liu Q, Yu H (2016) Community-based Link Prediction in Social Networks, pp. 341–348 Springer International Publishing

  42. Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Physical review E 78(4):046,110

    Article  Google Scholar 

  43. 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

    Article  Google Scholar 

  44. Lichtenwalter RN, Lussier JT, Chawla NV (2010) New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 243–252. ACM

  45. Lin D (1998) An information-theoretic definition of similarity. In: ICML, vol. 98, pp. 296–304. Citeseer

  46. Liu R, Ouyang Y, Rong W, Song X, Tang C, **ong Z (2016) Rating prediction based job recommendation service for college students. In: International conference on computational science and its applications, pp. 453–467. Springer

  47. Liu W, Lü L. (2010) Link prediction based on local random walk. EPL (Europhysics Letters) 89(5):58,007

    Article  Google Scholar 

  48. Lü L, ** CH, Zhou T (2009) Similarity index based on local paths for link prediction of complex networks. Physical Review E 80(4):046,122

    Article  Google Scholar 

  49. Lü L, Zhou T (2011) Link prediction in complex networks: a survey. Physica A: Statistical Mechanics and its Applications 390(6):1150–1170

    Article  Google Scholar 

  50. Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology 54(4):396–405

    Article  Google Scholar 

  51. Marchette DJ, Priebe CE (2008) Predicting unobserved links in incompletely observed networks. Computational Statistics & Data Analysis 52(3):1373–1386

    Article  MathSciNet  MATH  Google Scholar 

  52. Mavroforakis C, Garcia-Lebron R, Koutis I, Terzi E (2015) Spanning edge centrality: Large-scale computation and applications. In: Proceedings of the 24th international conference on world wide web, pp. 732–742. ACM

  53. Maxson CL, Hennigan K, Sloane DC (2003) Factors that influence public opinion of the police. US Department of Justice, Office of Justice Programs National Institute of Justice

  54. Michael JH (1997) Labor dispute reconciliation in a forest products manufacturing facilityl. Forest Products Journal 47:41–45

    Google Scholar 

  55. Mimno D, Wallach HM, Mccallum A (2007) Community-based link prediction with text

  56. Moore HT (1921) The comparative influence of majority and expert opinion. The American Journal of Psychology 32(1):16–20

    Article  Google Scholar 

  57. Mori J, Kajikawa Y, Kashima H, Sakata I (2012) Machine learning approach for finding business partners and building reciprocal relationships. Expert Systems with Applications 39(12):10,402– 10,407

    Article  Google Scholar 

  58. Newman ME (2001) Clustering and preferential attachment in growing networks. Physical review E 64(2):025,102

    Article  Google Scholar 

  59. Oh H, Chung MH, Labianca G (2004) Group social capital and group effectiveness: The role of informal socializing ties. Academy of management journal 47 (6):860–875

    Article  Google Scholar 

  60. Oshagan H (1996) Reference group influence on opinion expression. International journal of public opinion research 8(4):335–354

    Article  Google Scholar 

  61. Pan L, Zhou T, Lü L, Hu CK (2016) Predicting missing links and identifying spurious links via likelihood analysis. Scientific reports:6

  62. Qi X, Fuller E, Luo R, Zhang CQ (2015) A novel centrality method for weighted networks based on the kirchhoff polynomial. Pattern Recognition Letters 58:51–60

  63. Raeder T, Lizardo O, Hachen D, Chawla NV (2011) Predictors of short-term decay of cell phone contacts in a large scale communication network. Social Networks 33(4):245–257

    Article  Google Scholar 

  64. Ravasz E, Somera AL, Mongru DA, Oltvai ZN, Barabási AL (2002) Hierarchical organization of modularity in metabolic networks. Science 297 (5586):1551–1555

    Article  Google Scholar 

  65. Raymond R, Kashima H (2010) Fast and scalable algorithms for semi-supervised link prediction on static and dynamic graphs. In: Joint european conference on machine learning and knowledge discovery in databases, pp. 131–147. Springer

  66. Salton G, Mcgill MJ (1986) Introduction to modern information retrieval

  67. Schmutte IM (2015) Job referral networks and the determination of earnings in local labor markets. Journal of Labor Economics 33(1):1–32

    Article  Google Scholar 

  68. Shahriary SR, Shahriari M, Noor R (2015) A community-based approach for link prediction in signed social networks. Scientific Programming 2015:5

    Article  Google Scholar 

  69. Sie RL, Drachsler H, Bitter-Rijpkema M, Sloep P (2012) To whom and why should i connect? co-author recommendation based on powerful and similar peers. International Journal of Technology Enhanced Learning 4(1-2):121–137

    Article  Google Scholar 

  70. Sørensen T (1948) {A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons }. Biologiske Skrifter 5:1–34

    Google Scholar 

  71. Sparrowe RT, Liden RC, Wayne SJ, Kraimer ML (2001) Social networks and the performance of individuals and groups. Academy of management journal 44 (2):316–325

    Article  Google Scholar 

  72. Sun D, Zhou T, Liu JG, Liu RR, Jia CX, Wang BH (2009) Information filtering based on transferring similarity. Physical Review E 80(1):017,101

    Article  Google Scholar 

  73. Tan SY, Wu J, Lü L., Li MJ, Lu X (2016) Efficient network disintegration under incomplete information: the comic effect of link prediction. Scientific reports:6

  74. Teixeira AS, Monteiro PT, Carriço JA, Ramirez M, Francisco AP (2013) Spanning edge betweenness. In: Workshop on mining and learning with graphs, vol. 24, pp. 27–31

  75. Wang P, Xu B, Wu Y, Zhou X (2015) Link prediction in social networks: the state-of-the-art. Science China Information Sciences 58(1):1–38

    Google Scholar 

  76. Watts DJ, Dodds PS (2007) Influentials, networks, and public opinion formation. Journal of consumer research 34(4):441–458

  77. Wu S, Sun J, Tang J (2013) Patent partner recommendation in enterprise social networks. In: Proceedings of the sixth ACM international conference on web search and data mining, pp. 43–52. ACM

  78. Yu H, Braun P, Yıldırım MA, Lemmens I, Venkatesan K, Sahalie J, Hirozane-Kishikawa T, Gebreab F, Li N, Simonis N et al (2008) High-quality binary protein interaction map of the yeast interactome network. Science 322(5898):104–110

    Article  Google Scholar 

  79. Yu K, Chu W, Yu S, Tresp V, Xu Z (2006) Stochastic relational models for discriminative link prediction. In: Advances in neural information processing systems, pp. 1553–1560

  80. Zachary WW (1977) An information flow model for conflict and fission in small groups. Journal of anthropological research:452–473

  81. Zhu J, Hong J, Hughes JG (2002) Using markov models for web site link prediction. In: Proceedings of the thirteenth ACM conference on hypertext and hypermedia, pp. 169–170. ACM

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology (BHU) Varanasi, Varanasi, India

    Anupam Biswas & Bhaskar Biswas

Authors
  1. Anupam Biswas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bhaskar Biswas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anupam Biswas.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Biswas, A., Biswas, B. Community-based link prediction. Multimed Tools Appl 76, 18619–18639 (2017). https://doi.org/10.1007/s11042-016-4270-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-016-4270-9

Keywords

Search

Navigation