A Weighted path based Link Prediction in Social Networks using Bounded Length of Separation between Nodes

  • Authors

    • Srilatha P
    • Manjula R
    2018-10-02
    https://doi.org/10.14419/ijet.v7i4.10.20911
  • Social Networks, Link Prediction, Bounded Length.

  • The problem of link prediction in online social networks like facebook, myspace, Hi5 and in other domains like biological network of molecules, gene network to model disease have became very popular because of the structural connections and relationships  among the entities. The classical methods of link prediction based on the topological structure of the graph exploit all different paths of the network which are being computationally expensive for large size of networks. In this paper, incorporating  the small world phenomenon, the proposed algorithm traverses all the paths of bounded length by considering clustering information and the connection pattern of the edges as weights on the edges in the graph. As a result, the proposed algorithm will be able to predict accurately than the existing link prediction algorithms. Our analysis and experiment on real world networks shows that our algorithm outperforms other approaches in terms of time complexity and the prediction accuracy.

     

     

  • References

    1. [1] Ryan N Lichtenwalter, Jake T Lussier, and Nitesh V Chawla, “New perspectives and methods in link predictionâ€. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 243–252. ACM, 2010.

      [2] Shengxian Wan, Yanyan Lan, Jiafeng Guo, Chaosheng Fan, and Xueqi Cheng. “Informational friend recommendation in social mediaâ€. In Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval, pages 1045–1048. ACM, 2013.

      [3] Jacob W Bartel and Prasun Dewan. “Evolving friend lists in social networksâ€. In Proceedings of the 7th ACM Conference on Recommender Systems, pages 435–438. ACM, 2013.

      [4] Maryam Fazel-Zarandi, Hugh J Devlin, Yun Huang, and Noshir Contractor. “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, pages 41–48. ACM, 2011.

      [5] Mark EJ Newman. “Clustering and preferential attachment in growing networksâ€. Physical review E, 64(2):025102, 2001.

      [6] Yangyang Liu, Chengli Zhao, Xiaojie Wang, Qiangjuan Huang, Xue Zhang, and Dongyun Yi. “The degree-related clustering coefficient and its application to link predictionâ€. Physica A: Statistical Mechanics and its Applications, 454:24–33, 2016.

      [7] Tsuyoshi Murata and Sakiko Moriyasu. “Link prediction based on structural properties of online social networksâ€. New Generation Computing, 26(3):245–257, 2008.

      [8] Abir De, Niloy Ganguly, and Soumen Chakrabarti. “Discriminative link prediction using local links, node features and community structureâ€. In Data Mining (ICDM), 2013 IEEE 13th International Conference on, pages 1009–1018. IEEE, 2013.

      [9] Jing Wang and Lili Rong. “Similarity index based on the information of neighbor nodes for link prediction of complex networkâ€. Modern Physics Letters B, 27(06):1350039, 2013.

      [10] Ismail Güne¸s, ¸Sule Gündüz-Ö˘güdücü, and Zehra Çataltepe. “Link prediction using time series of neighborhood-based node similarity scoresâ€. Data Mining and Knowledge Discovery, 30(1):147–180, 2016.

      [11] Glen Jeh and Jennifer Widom. “Simrank: a measure of structural-context similarityâ€. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538–543. ACM, 2002.

      [12] Bai Meng, Hu Ke, and Tang Yi. “Link prediction based on a semi-local similarity index.†Chinese Physics B, 20(12):128902, 2011.

      [13] Weiping Liu and Linyuan Lü. “Link prediction based on local random walkâ€. EPL (Europhysics Letters), 89(5):58007, 2010.

      [14] Alexis Papadimitriou, Panagiotis Symeonidis, and Yannis Manolopoulos. “Fast and accurate link prediction in social networking systems.†Journal of Systems and Software, 85(9):2119–2132, 2012.

      [15] Pulipati Srilatha and Ramakrishnan Manjula. “Similarity index based link prediction algorithms in social networks: A survey.†Journal of Telecommunications and Information Technology, (2):87, 2016.

      [16] Linyuan Lü and Tao Zhou. “Link prediction in complex networks: A survey.†Physica A: statistical mechanics and its applications, 390(6):1150–1170, 2011.

      [17] Michelle Girvan and Mark EJ Newman. “Community structure in social and biological networks.†Proceedings of the national academy of sciences, 99(12):7821–7826, 2002.

      [18] Pasquale DeMeo, Emilio Ferrara, Giacomo Fiumara, and Angela Ricciardello. “A novel measure of edge centrality in social networksâ€. Knowledge-based systems, 30:136–150, 2012.

      [19] Ulrik Brandes. “A faster algorithm for betweenness centralityâ€. Journal of mathematical sociology, 25(2):163–177, 2001.

      [20] James A Hanley and Barbara J McNeil. “The meaning and use of the area under a receiver operating characteristic (roc) curveâ€. Radiology, 143(1):29–36, 1982.

      [21] Jesse Davis and Mark Goadrich. “The relationship between precision-recall and roc curvesâ€. In Proceedings of the 23rd international conference on Machine learning, pages 233–240. ACM, 2006.

      [22] Bolun Chen, Ling Chen, and Bin Li. “A fast algorithm for predicting links to nodes of interestâ€. Information Sciences, 329:552–567, 2016.

      [23] Francois Lorrain and Harrison C White. “Structural equivalence of individuals in social networksâ€. The Journal of mathematical sociology, 1(1):49–80, 1971.

      [24] Gerard Salton and Michael J McGill. “Introduction to modern information retrievalâ€. 1986.

      [25] Paul Jaccard. “Étude comparative de la distribution florale dans une portion des alpes et des juraâ€. Bull Soc Vaudoise Sci Nat, 37:547–579, 1901.

      [26] Thorvald Sørensen. “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â€. Biol. Skr., 5:1–34, 1948

  • Downloads

  • How to Cite

    P, S., & R, M. (2018). A Weighted path based Link Prediction in Social Networks using Bounded Length of Separation between Nodes. International Journal of Engineering & Technology, 7(4.10), 274-277. https://doi.org/10.14419/ijet.v7i4.10.20911