Một biện pháp đo lường độ tương đồng mới cho dự đoán liên kết trong mạng đơn và mạng lưỡng phân

Social Network Analysis and Mining - Tập 11 - Trang 1-14 - 2021
Purushottam Kumar1, Dolly Sharma1
1Department of Computer Science and Engineering, Shiv Nadar University, Gautam Buddha Nagar, India

Tóm tắt

Mạng lưới hiện diện ở khắp mọi nơi và các ứng dụng của chúng trong nhiều lĩnh vực như khoa học máy tính, khoa học sinh học, kinh tế học, và kỹ thuật hóa học đã thu hút sự chú ý của nhiều nhà nghiên cứu. Nhiều hệ thống phức tạp trong thế giới thực có thể được biểu diễn bằng mạng hoặc đồ thị. Dự đoán liên kết là một trong những nhiệm vụ quan trọng nhất trong phân tích mạng, do đó thu hút rất nhiều sự quan tâm nghiên cứu trong những thập kỷ qua. Trong bài báo này, chúng tôi giới thiệu một thuật toán mới cho dự đoán liên kết hoạt động hiệu quả cho cả đồ thị đơn và đồ thị lưỡng phân. Thuật toán mới của chúng tôi dựa trên khái niệm về vector riêng và khoảng cách ngắn nhất giữa các nút. Chúng tôi đã sử dụng định lý Peron–Frobenius về tầm quan trọng của nút cho dự đoán liên kết. Bốn chỉ số, bao gồm AUC, độ chính xác, sức mạnh dự đoán và độ chính xác@K, đã được tính toán và so sánh với mười bốn thuật toán cơ sở để kiểm tra hiệu suất của thuật toán đề xuất. Việc kiểm tra được thực hiện trên mười ba tập dữ liệu, và kết quả thực nghiệm cho thấy phương pháp đề xuất vượt trội hơn so với thuật toán cơ sở dựa trên bốn chỉ số đã cho.

Từ khóa

#mạng lưới #dự đoán liên kết #đồ thị đơn #đồ thị lưỡng phân #thuật toán Peron-Frobenius

Tài liệu tham khảo

Adamic LA, Adar E (2003) Friends and neighbors on the web. Social Netw 25(3):211–230 Aghabozorgi F, Khayyambashi MR (2018) A new similarity measure for link prediction based on local structures in social networks. Phys A 501:12–23 Ahmad I, Akhtar MU, Noor S, Shahnaz A (2020) Missing link prediction using common neighbor and centrality based parameterized algorithm. Sci Rep 10(1):1–9 Aiello LM, Barrat A, Schifanella R, Cattuto C, Markines B, Menczer F (2012) Friendship prediction and homophily in social media. ACM Trans Web (TWEB) 6(2):1–33 Allali O, Magnien C, Latapy M (2011) Link prediction in bipartite graphs using internal links and weighted projection. In: 2011 IEEE conference on computer communications workshops (INFOCOM WKSHPS), IEEE, pp 936–941 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. Netw Model Anal Health Inf Bioinform 1(1–2):27–36 Aslan S, Kaya B, Kaya M (2019) Predicting potential links by using strengthened projections in evolving bipartite networks. Phys A 525:998–1011 Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512 Barabâsi AL, Jeong H, Néda Z, Ravasz E, Schubert A, Vicsek T (2002) Evolution of the social network of scientific collaborations. Phys A 311(3–4):590–614 Benchettara N, Kanawati R, Rouveirol C (2010) Supervised machine learning applied to link prediction in bipartite social networks. In: 2010 International Conference on Advances in Social Networks Analysis and Mining, IEEE, pp 326–330 Bütün E, Kaya M, Alhajj R (2018) Extension of neighbor-based link prediction methods for directed, weighted and temporal social networks. Inf Sci 463:152–165 Cannistraci CV, Alanis-Lobato G, Ravasi T (2013) From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks. Sci Rep 3:1613 Chang YJ, Kao HY (2012) Link prediction in a bipartite network using wikipedia revision information. In: 2012 Conference on Technologies and Applications of Artificial Intelligence, IEEE, pp 50–55 Chuan PM, Ali M, Khang TD, Dey N et al (2018) Link prediction in co-authorship networks based on hybrid content similarity metric. Appl Intell 48(8):2470–2486 Daminelli S, Thomas JM, Durán C, Cannistraci CV (2015) Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks. New J Phys 17(11):113037 Davis A, Gardner BB, Gardner MR (1941) Deep South; a social anthropological study of caste and class. The University of Chicago Press, Chicago Durán C, Daminelli S, Thomas JM, Haupt VJ, Schroeder M, Cannistraci CV (2018) Pioneering topological methods for network-based drug-target prediction by exploiting a brain-network self-organization theory. Briefings Bioinform 19(6):1183–1202 Gao M, Chen L, Li B, Li Y, Liu W, Yc Xu (2017) Projection-based link prediction in a bipartite network. Inf Sci 376:158–171 Getoor L (2000) Learning probabilistic relational models. In: International Symposium on Abstraction, Reformulation, and Approximation, Springer, pp 322–323 Gleiser PM, Danon L (2003) Community structure in jazz. Adv Complex Syst 6(04):565–573 Hanley JA, McNeil BJ (1982) The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology 143(1):29–36 Harper FM, Konstan JA (2016) The movielens datasets: history and context. ACM TIIS 5(4):19 Herlocker JL, Konstan JA, Terveen LG, Riedl JT (2004) Evaluating collaborative filtering recommender systems. ACM Trans Inf Syst (TOIS) 22(1):5–53 Jawed M, Kaya M, Alhajj R (2015) Time frame based link prediction in directed citation networks. In: 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), IEEE, pp 1162–1168 Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43 Kaya M, Jawed M, Bütün E, Alhajj R (2017) Unsupervised link prediction based on time frames in weighted–directed citation networks. In: Trends in Social Network Analysis, Springer, pp 189–205 Kleinberg JM (2000) Navigation in a small world. Nature 406(6798):845 konect (2016a) U. rovira i virgili network dataset – KONECT. http://konect.uni-koblenz.de/networks/arenas-email konect (2016b) Us power grid network dataset – KONECT. http://konect.uni-koblenz.de/networks/opsahl-powergrid konect (2017) Zachary karate club network dataset – KONECT. http://konect.cc/networks/ucidata-zachary Kunegis J, De Luca EW, Albayrak S (2010) The link prediction problem in bipartite networks. In: International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, Springer, pp 380–389 Lee DD, Seung HS (2001) Algorithms for non-negative matrix factorization. In: Advances in neural information processing systems, pp 556–562 Li J, Peng J, Liu S, Ji X, Li X, Hu X (2020) Link prediction in directed networks utilizing the role of reciprocal links. IEEE Access 8:28668–28680 Li RH, Yu JX, Liu J (2011) Link prediction: the power of maximal entropy random walk. In: Proceedings of the 20th ACM international conference on Information and knowledge management, ACM, pp 1147–1156 Li X, Chen H (2013) Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach. Decis Support Syst 54(2):880–890 Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. J Am Soc Inform Sci Technol 58(7):1019–1031 Lin Y, Desouza KC, Roy S (2010) Measuring agility of networked organizational structures via network entropy and mutual information. Appl Math Comput 216(10):2824–2836 Lorrain F, White HC (1971) Structural equivalence of individuals in social networks. J Math Sociol 1(1):49–80 Lü L, Zhou T (2011) Link prediction in complex networks: A survey. Physica A 390(6):1150–1170 Lü L, Pan L, Zhou T, Zhang YC, Stanley HE (2015) Toward link predictability of complex networks. Proc Nat Acad Sci 112(8):2325–2330 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. Behav Ecol Sociobiol 54(4):396–405 Nassar H, Benson AR, Gleich DF (2020) Neighborhood and pagerank methods for pairwise link prediction. Social Network Analysis and Mining 10(1):1–13 Newman ME (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64(2):025102 Pizzuti C (2008) Ga-net: A genetic algorithm for community detection in social networks. In: International conference on parallel problem solving from nature, Springer, pp 1081–1090 Rezaeipanah A, Ahmadi G, Matoori SS (2020) A classification approach to link prediction in multiplex online ego-social networks. Social Netw Analys Mining 10(1):27 Salton G (1983) Some research problems in automatic information retrieval. ACM SIGIR Forum, ACM New York, NY, USA 17:252–263 Shakibian H, Charkari NM (2017) Mutual information model for link prediction in heterogeneous complex networks. Scientific reports 7:44981 Shams B, Haratizadeh S (2016) Sibrank: Signed bipartite network analysis for neighbor-based collaborative ranking. Physica A 458:364–377 Spizzirri L (2011) Justification and application of eigenvector centrality. Algebra in Geography: Eigenvectors of Network Spring N, Mahajan R, Wetherall D, Anderson T (2004) Measuring isp topologies with rocketfuel. IEEE/ACM Trans Networking 12(1):2–16 Talasu N, Jonnalagadda A, Pillai SSA, Rahul J (2017) A link prediction based approach for recommendation systems. In: 2017 international conference on advances in computing, communications and informatics (ICACCI), IEEE, pp 2059–2062 Tan F, Xia Y, Zhu B (2014) Link prediction in complex networks: a mutual information perspective. PLoS ONE 9(9) Von Mering C, Krause R, Snel B, Cornell M, Oliver SG, Fields S, Bork P (2002) Comparative assessment of large-scale data sets of protein-protein interactions. Nature 417(6887):399–403 Wahid-Ul-Ashraf A, Budka M, Musial K (2019) How to predict social relationships-physics-inspired approach to link prediction. Phys A 523:1110–1129 Wang H, Hu W, Qiu Z, Du B (2017) Nodes’ evolution diversity and link prediction in social networks. IEEE Trans Knowl Data Eng 29(10):2263–2274 Wang P, Xu B, Wu Y, Zhou X (2015) Link prediction in social networks: the state-of-the-art. Sci China Inf Sci 58(1):1–38 Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(1):440–442 Xia S, Dai B, Lim EP, Zhang Y, Xing C (2012) Link prediction for bipartite social networks: the role of structural holes. In: Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012), IEEE Computer Society, pp 153–157 Yamanishi Y, Araki M, Gutteridge A, Honda W, Kanehisa M (2008) Prediction of drug-target interaction networks from the integration of chemical and genomic spaces. Bioinformatics 24(13):i232–i240 Yildirim MA, Coscia M (2014) Using random walks to generate associations between objects. PLoS ONE 9(8):e104813 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 Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33(4):452–473 Zhou T, Lü L, Zhang YC (2009) Predicting missing links via local information. Eur Phys J B 71(4):623–630 Zhu M, Cao T, Jiang X (2014) Using clustering coefficient to construct weighted networks for supervised link prediction. Soc Netw Anal Min 4(1):215