Signed Social Network Vulnerability Analysis in Terms of Clustering coefficient and Balance Theory

Document Type : Original Article

Authors

1 Electrical and Computer Engineering Group, Golpayegan College of Engineering, Isfahan University of Technology, Golpayegan, Iran,

2 Department of Computer Engineering, Abadan Branch, Islamic Azad University, Abadan, Iran

Abstract

The robustness of a social network in response to unexpected events is still challenging for real-world networks. This paper addresses the challenge of evaluating social network robustness against unexpected events, particularly in real-world signed networks. We analyze the clustering vulnerability and balance of Signed Social Networks (SSNs) under the failure of important nodes. The main objective is to identify the critical nodes whose removal disrupts the network by weakening its clustering. It is evaluated by the Average Local Clustering Coefficient guided by the balance degree of the networks. To identify critical nodes, we propose parameter-based greedy strategies that remove nodes based on specific criteria. We conduct a comprehensive analysis of the real and synthetic SSNs generated by different well-known models and also online datasets. Our experiments demonstrate that removing a small percentage of nodes with the highest "Fans Minus Freaks (FMF)" value significantly reduces the network's clustering coefficient. Interestingly, centrality and PageRank metrics also play a role, but to a lesser extent, ranking second and third in terms of critical impact, respectively.

Keywords

Main Subjects

References

[1] S. Wang, Y. Du, and Y. Deng, "A new measure of identifying influential nodes: Efficiency centrality," Communications in Nonlinear Science and Numerical Simulation, vol. 47, pp. 151-163, 2017.
[2] X. Wang, B. Jiang, and B. Li, "Opinion dynamics on social networks," Acta Mathematica Scientia, vol. 42, no. 6, pp. 2459-2477, 2022.
[3] L. Fei, H. Mo, and Y. Deng, "A new method to identify influential nodes based on combining of existing centrality measures," Modern Physics Letters B, vol. 31, no. 26, p. 1750243, 2017.
[4] L. Lü, D. Chen, X.-L. Ren, Q.-M. Zhang, Y.-C. Zhang, and T. Zhou, "Vital nodes identification in complex networks," Physics Reports, vol. 650, pp. 1-63, 2016.
[5] S. Kumar, A. Mallik, A. Khetarpal, and B. Panda, "Influence maximization in social networks using graph embedding and graph neural network," Information Sciences, vol. 607, pp. 1617-1636, 2022.
[6] D. Cartwright and F. Harary, "Structural balance: a generalization of Heider's theory," Psychological review, vol. 63, no. 5, p. 277, 1956.
[7] X. He, R. Zhang, and B. Zhu, "A generalized modularity for computing community structure in fully signed networks," Complexity, vol. 2023, 2023.
[8] D. J. Watts and S. H. Strogatz, "Collective dynamics of ‘small-world’networks," nature, vol. 393, no. 6684, p. 440, 1998.
[9] J. Kunegis, A. Lommatzsch, and C. Bauckhage, "The slashdot zoo: mining a social network with negative edges," in Proceedings of the 18th international conference on World wide web, 2009: ACM, pp. 741-750.
[10]  L. S. Alla and A. S. Kare, "Opinion Maximization in Signed Social Networks Using Centrality Measures and Clustering Techniques," in International Conference on Distributed Computing and Intelligent Technology, 2023: Springer, pp. 125-140.
[11]  E. Estrada, "Rethinking structural balance in signed social networks," Discrete Applied Mathematics, vol. 268, pp. 70-90, 2019.
[12] T. Minh Pham, I. Kondor, R. Hanel, and S. Thurner, "The effect of social balance on social fragmentation," Journal of the Royal Society Interface, vol. 17, no. 172, p. 20200752, 2020.
[13] S. Aref, L. Dinh, R. Rezapour, and J. Diesner, "Multilevel structural evaluation of signed directed social networks based on balance theory," Scientific reports, vol. 10, no. 1, pp. 1-12, 2020.
[14] F. Adriaens and S. Apers, "Testing properties of signed graphs," arXiv preprint arXiv:2102.07587, 2021.
[15] L. Dinh, R. Rezapour, L. Jiang, and J. Diesner, "Enhancing structural balance theory and measurement to analyze signed digraphs of real-world social networks," Frontiers in Human Dynamics, vol. 4, p. 1028393, 2023.
[16] A. Arya, P. K. Pandey, and A. Saxena, "Balanced and Unbalanced Triangle Count in Signed Networks," IEEE Transactions on Knowledge and Data Engineering, 2023.
[17] س. مرادی, ج. باقرزاده, and ا. مهدی پور, "Modeling homogeneous contact distribution of nodes and its application in routing in Mobile Social Networks," مجله مهندسی برق دانشگاه تبریز, vol. 51, no. 4, pp. 431-441, 2021. [Online]. Available: https://tjee.tabrizu.ac.ir/article_14667_46e8382c34f8e83deb2d6ba7a1c3cd74.pdf.
[18] ه. پروین, پ. مرادی, and ش. اسماعیلی, "ترکیب تجزیه نامنفی ماتریسی با روابط اعتماد برای توصیه در شبکه‌های اجتماعی," مجله مهندسی برق دانشگاه تبریز, vol. 50, no. 2, pp. 605-618, 2020. [Online]. Available: https://tjee.tabrizu.ac.ir/article_10954_7ce1afbc4106f8245f364156e217c4ae.pdf.
[19] S. Dhelim, N. Aung, M. T. Kechadi, H. Ning, L. Chen, and A. Lakas, "Trust2Vec: Large-scale IoT trust management system based on signed network embeddings," IEEE Internet of Things Journal, vol. 10, no. 1, pp. 553-562, 2022.
[20] H. Du, X. He, and M. W. Feldman, "Structural balance in fully signed networks," Complexity, vol. 21, no. S1, pp. 497-511, 2016.
[21] D. Feng, R. Altmeyer, D. Stafford, N. A. Christakis, and H. H. Zhou, "Testing for balance in social networks," Journal of the American Statistical Association, vol. 117, no. 537, pp. 156-174, 2022.
[22] L. Shi, W. Li, M. Shi, K. Shi, and Y. Cheng, "Opinion Polarization Over Signed Social Networks With Quasi Structural Balance," IEEE Transactions on Automatic Control, 2023.
[23] M. A. Alim, N. P. Nguyen, T. N. Dinh, and M. T. Thai, "Structural vulnerability analysis of overlapping communities in complex networks," in Proceedings of the 2014 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT)-Volume 01, 2014: IEEE Computer Society, pp. 5-12.
[24] M. N. Abadeh and M. Mirzaie, "Ranking Resilience Events in IoT Industrial Networks," in 2021 5th International Conference on Internet of Things and Applications (IoT), 2021: IEEE, pp. 1-5.
[25] T. N. Dinh, Y. Xuan, M. T. Thai, P. M. Pardalos, and T. Znati, "On new approaches of assessing network vulnerability: hardness and approximation," IEEE/ACM Transactions on Networking, vol. 20, no. 2, pp. 609-619, 2012.
[26] R. Albert, H. Jeong, and A.-L. Barabási, "Error and attack tolerance of complex networks," nature, vol. 406, no. 6794, p. 378, 2000.
[27] P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, "Attack vulnerability of complex networks," Physical review E, vol. 65, no. 5, p. 056109, 2002.
[28] S. Allesina and M. Pascual, "Googling food webs: can an eigenvector measure species' importance for coextinctions?," PLoS computational biology, vol. 5, no. 9, p. e1000494, 2009.
[29] T. H. Grubesic, T. C. Matisziw, A. T. Murray, and D. Snediker, "Comparative approaches for assessing network vulnerability," International Regional Science Review, vol. 31, no. 1, pp. 88-112, 2008.
[30]  J. Leskovec, D. Huttenlocher, and J. Kleinberg, "Signed networks in social media," in Proceedings of the SIGCHI conference on human factors in computing systems, 2010: ACM, pp. 1361-1370.
[31] T. P. Peixoto and S. Bornholdt, "Evolution of robust network topologies: Emergence of central backbones," Physical review letters, vol. 109, no. 11, p. 118703, 2012.
[32] D. S. Callaway, M. E. Newman, S. H. Strogatz, and D. J. Watts, "Network robustness and fragility: Percolation on random graphs," Physical review letters, vol. 85, no. 25, p. 5468, 2000.
[33] A. Veremyev, O. A. Prokopyev, and E. L. Pasiliao, "Critical nodes for distance‐based connectivity and related problems in graphs," Networks, vol. 66, no. 3, pp. 170-195, 2015.
[34] A. Veremyev, O. A. Prokopyev, and E. L. Pasiliao, "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, vol. 28, no. 1, pp. 233-273, 2014.
[35] X. Chen, "System vulnerability assessment and critical nodes identification," Expert Systems with Applications, vol. 65, pp. 212-220, 2016.
[36] T. Gomes et al., "A survey of strategies for communication networks to protect against large-scale natural disasters," in Resilient Networks Design and Modeling (RNDM), 2016 8th International Workshop on, 2016: IEEE, pp. 11-22.
[37] G. Kalna and D. J. Higham, "A clustering coefficient for weighted networks, with application to gene expression data," Ai Communications, vol. 20, no. 4, pp. 263-271, 2007.
[38] A. Kuhnle, N. P. Nguyen, T. N. Dinh, and M. T. Thai, "Vulnerability of clustering under node failure in complex networks," Social Network Analysis and Mining, vol. 7, no. 1, pp. 1-15, 2017.
[39] H. Liu, Z. Tian, A. Huang, and Z. Yang, "Analysis of vulnerabilities in maritime supply chains," Reliability Engineering & System Safety, vol. 169, pp. 475-484, 2018.
[40] Y. E. Malashenko, I. A. Nazarova, and N. y. M. Novikova, "Analysis of cluster damages in network systems," Computational Mathematics and Mathematical Physics, vol. 60, no. 2, pp. 341-351, 2020.
[41] N. P. Nguyen, M. A. Alim, Y. Shen, and M. T. Thai, "Assessing network vulnerability in a community structure point of view," in Advances in Social Networks Analysis and Mining (ASONAM), 2013 IEEE/ACM International Conference on, 2013: IEEE, pp. 231-235.
[42] A. Kuhnle, N. P. Nguyen, T. N. Dinh, and M. T. Thai, "Vulnerability of clustering under node failure in complex networks," Social Network Analysis and Mining, vol. 7, no. 1, p. 8, 2017.
[43] Z. Ertem, A. Veremyev, and S. Butenko, "Detecting large cohesive subgroups with high clustering coefficients in social networks," Social Networks, vol. 46, pp. 1-10, 2016.
[44] E. J. Bienenstock and P. Bonacich, Balancing efficiency and vulnerability in social networks. na, 2002.
[45] A. Kumari, R. K. Behera, K. S. Sahoo, A. Nayyar, A. Kumar Luhach, and S. Prakash Sahoo, "Supervised link prediction using structured‐based feature extraction in social network," Concurrency and Computation: practice and Experience, vol. 34, no. 13, p. e5839, 2022.
[46] J. Scott and P. J. Carrington, The SAGE handbook of social network analysis. SAGE publications, 2011.
[47] B. Yang, W. Cheung, and J. Liu, "Community mining from signed social networks," IEEE transactions on knowledge and data engineering, vol. 19, no. 10, pp. 1333-1348, 2007.
[48] J. Huang et al., "Negative can be positive: Signed graph neural networks for recommendation," Information Processing & Management, vol. 60, no. 4, p. 103403, 2023.
[49] W. Xing and A. Ghorbani, "Weighted pagerank algorithm," in Proceedings. Second Annual Conference on Communication Networks and Services Research, 2004., 2004: IEEE, pp. 305-314.
[50] M. Pasquinelli, "Google’s PageRank algorithm: A diagram of cognitive capitalism and the rentier of the common intellect," Deep search: The politics of search beyond Google, pp. 152-162, 2009.
[51] J. Kunegis, A. Lommatzsch, and C. Bauckhage, "The slashdot zoo: mining a social network with negative edges," presented at the Proceedings of the 18th international conference on World wide web, Madrid, Spain, 2009.
[52] P. Bonacich and P. Lloyd, "Calculating status with negative relations," Social networks, vol. 26, no. 4, pp. 331-338, 2004.
[53] C. d. Kerchove and P. V. Dooren, "The pagetrust algorithm: How to rank web pages when negative links are allowed?," in Proceedings of the 2008 SIAM International Conference on Data Mining, 2008: SIAM, pp. 346-352.
[54] L. Page, S. Brin, R. Motwani, and T. Winograd, "The PageRank citation ranking: Bringing order to the web," Stanford InfoLab, 1999.
[55] M. Shahriari and M. Jalili, "Ranking nodes in signed social networks," Social network analysis and mining, vol. 4, no. 1, p. 172, 2014.
[56] A. Teixeira, F. C. Santos, and A. P. Francisco, Emergence of Social Balance in Signed Networks. 2017.
[57]  D. Schoch, "signnet: An R package for analyzing signed networks," Journal of Open Source Software, vol. 8, no. 81, p. 4987, 2023.
[58] G. Facchetti, G. Iacono, and C. Altafini, "Computing global structural balance in large-scale signed social networks," Proceedings of the National Academy of Sciences, vol. 108, no. 52, pp. 20953-20958, 2011.

Files

Share

How to cite

Statistics