Transitivity Demolition and the Fall of Social Networks

IEEE Access - Tập 5 - Trang 15913-15926 - 2017
Hung T. Nguyen1, Nam P. Nguyen2, Tam Vu3, Huan X. Hoang4, Thang N. Dinh1
1Computer Science Department, Virginia Commonwealth University, Richmond, VA, USA
2Computer and Information Sciences Department, Towson University, Towson, MD, USA
3Computer Science and Engineering Department, University of Colorado, Denver, CO, USA
4Information Technology Department, Vietnam National University, Hanoi, Vietnam

Tóm tắt

In this paper, we study crucial elements of a complex network, namely its nodes and connections, which play a key role in maintaining the network's structure and function under unexpected structural perturbations of nodes and edges removal. Specifically, we want to identify vital nodes and edges whose failure (either random or intentional) will break the most number of connected triples (or triangles) in the network. This problem is extremely important, because connected triples form the foundation of strong connections in many real-world systems, such as mutual relationships in social networks, reliable data transmission in communication networks, and stable routing strategies in mobile networks. Disconnected triples, analog to broken mutual connections, can greatly affect the network's structure and disrupt its normal function, which can further lead to the corruption of the entire system. The analysis of such crucial elements will shed light on key factors behind the resilience and robustness of many complex systems in practice. We formulate the analysis under multiple optimization problems and show their intractability. We next propose efficient approximation algorithms, namely, DAK-n and DAK-e, which guarantee an (1 - 1/e)-approximate ratio (compared with the overall optimal solutions) while having the same time complexity as the best triangle counting and listing algorithm on power-law networks. This advantage makes our algorithms scale extremely well even for very large networks. In an application perspective, we perform comprehensive experiments on real social traces with millions of nodes and billions of edges. Empirical results indicate that our approaches achieve comparably better solution quality while are up to 100× faster than the current state-of-the-art methods.

Từ khóa

#Triangle breaking #social networks #approximation algorithms

Tài liệu tham khảo

10.1007/BF02523189

schank, 2005, Finding, counting and listing all triangles in large graphs, an experimental study, Proceedings of the 4th International Conference on Experimental and Efficient Algorithms, 606, 10.1007/11427186_54

10.1109/INFCOM.2013.6566734

10.1109/TNET.2013.2290714

10.1145/2309996.2310024

10.1103/PhysRevLett.85.5468

10.1109/WI-IAT.2014.10

10.1145/2492517.2492644

10.1080/15427951.2014.950875

10.1109/ICDM.2013.24

fiedler, 1973, Algebraic connectivity of graphs, Czechoslovak Math J, 23, 298, 10.21136/CMJ.1973.101168

10.1109/TCOM.1970.1090419

10.1103/PhysRevLett.109.118703

10.1109/PASSAT/SocialCom.2011.16

10.1103/PhysRevE.65.056109

10.1145/1281192.1281239

10.1177/0160017607308679

10.1007/s10115-014-0800-9

10.1109/TNET.2011.2128879

10.1111/j.1468-2257.2008.00447.x

10.1109/TNET.2014.2317486

10.1109/MILCOM.2011.6127492

10.1109/SFCS.2001.959927

10.1109/JSAC.2013.130602

10.1126/science.1207055

boyd, 2016, Friendster lost steam. Is myspace just a fad?, Apophenia Blog, 1, 1

10.1145/1963405.1963491

travis, 2013, Cyberspace Law Censorship Regulation Internet, 10.4324/9780203384756

ponton, 2013, Weighted clustering coefficient maximization for air transportation networks, Proc Eur Control Conf (ECC), 866

10.1109/TMC.2016.2524571

10.1109/TNET.2011.2170849

chan, 2014, Make It or Break It Manipulating Robustness in Large Networks, 325

10.1038/35019019

10.1371/journal.pcbi.1000494

dinh, 2015, Breaking Bad Finding Triangle-Breaking Points in Large Networks, 285

watts, 1998, Collective dynamics of ‘small-world’ networks, Nature, 393, 440, 10.1038/30918

10.1109/MILCOM.2010.5680488

centola, 2010, The spread of behavior in an online social network experiment, Science, 329, 1194, 10.1126/science.1185231

10.1145/1232722.1232727

lü, 2011, The small world yields the most effective information spreading, New J Phys, 13, 123005, 10.1088/1367-2630/13/12/123005

10.1186/1471-2458-13-784

10.1016/S0378-4371(02)00736-7

10.1063/1.4833995

vazirani, 2001, Approximation Algorithms

10.1023/B:JOCO.0000038913.96607.c2

10.1016/S0378-4371(00)00018-2

10.1137/0210021

10.1145/1142351.1142388

bar-yossef, 2002, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proc 13th Annu ACM-SIAM Symp Discrete Algorithms, 623

10.1016/j.jalgor.2004.04.002

jowhari, 2005, New streaming algorithms for counting triangles in graphs, Computing and Combinatorics, 710, 10.1007/11533719_72

Thông tin
Thông tin xuất bản

IEEE Access

Tập 5

15913-15926

Thông tin tác giả