Eigen-Optimization on Large Graphs by Edge Manipulation

Abstract

Large graphs are prevalent in many applications and enable a variety of information dissemination processes, e.g., meme, virus, and influence propagation. How can we optimize the underlying graph structure to affect the outcome of such dissemination processes in a desired way (e.g., stop a virus propagation, facilitate the propagation of a piece of good idea, etc)? Existing research suggests that the leading eigenvalue of the underlying graph is the key metric in determining the so-called epidemic threshold for a variety of dissemination models. In this paper, we study the problem of how to optimally place a set of edges (e.g., edge deletion and edge addition) to optimize the leading eigenvalue of the underlying graph, so that we can guide the dissemination process in a desired way. We propose effective, scalable algorithms for edge deletion and edge addition, respectively. In addition, we reveal the intrinsic relationship between edge deletion and node deletion problems. Experimental results validate the effectiveness and efficiency of the proposed algorithms.

References

1. Deepak Agarwal, Andrei Z. Broder, Deepayan Chakrabarti, Dejan Diklic, Vanja Josifovski, and Mayssam Sayyadian. 2007. Estimating rates of rare events at multiple resolutions. In KDD. San Jose, CA, USA, 16--25.
2. Lars Backstrom and Jure Leskovec. 2011. Supervised random walks: Predicting and recommending links in social networks. In WSDM. Hong Kong, China, 635--644.
3. Tanya Berger-Wolf and others. 2011. Working for influence: Effect of network density and modularity on diffusion in networks. In Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW). IEEE, Vancouver, Canada, 933--940.
4. Alex Beutel, B. Aditya Prakash, Roni Rosenfeld, and Christos Faloutsos. 2012. Interacting viruses in networks: Can both survive? In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 426--434.
5. Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. 1992. A theory of fads, fashion, custom, and cultural change in informational cascades. J. Pol. Economy 100, 5 (October 1992), 992--1026.
6. Adrian N. Bishop and Iman Shames. 2011. Link operations for slowing the spread of disease in complex networks. EPL (Europhysics Letters) 95.1 (2011), 18005.
7. Linda Briesemeister, Patric Lincoln, and Philip Porras. 2003. Epidemic profiles and defense of scale-free networks. WORM 2003 (Oct. 27 2003), 67--75.
8. Andrei Z. Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet L. Wiener. 2000. Graph structure in the Web. Computer Networks 33, 1--6 (2000), 309--320.
9. Chen Chen, Jingrui He, Nadya Bliss, and Hanghang Tong. 2015. On the connectivity of multi-layered networks: Models, measures and optimal control. In ICDM. Atlantic City, NJ, USA, 715--720.
10. Chen Chen and Hanghang Tong. 2015. Fast eigen-functions tracking on dynamic graphs. In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, Vancouver, BC, CA, 559--567.
11. Chen Chen, Hanghang Tong, B. Aditya Prakash, Charalampos E. Tsourakakis, Tina Eliassi-Rad, Christos Faloutsos, and Duen Horng Chau. 2016. Node immunization on large graphs: Theory and algorithms. Knowledge and Data Engineering, IEEE Transactions on 28, 1 (2016), 113--126.
12. Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD. Washington DC, USA, 1029--1038.
13. Samik Datta, Anirban Majumder, and Nisheeth Shrivastava. 2010. Viral marketing for multiple products. In ICDM. Sydney, Australia, 118--127.
14. L. C. Freeman. 1977. A set of measures of centrality based on betweenness. Sociometry (1977), 35--41.
15. A. Ganesh, E. L. Massouli, and D. Towsley. 2005. The effect of network topology on the spread of epidemics. In INFOCOM. Miami, FL, USA, 1455--1466.
16. Yong Ge, Hui Xiong, Alexander Tuzhilin, Keli Xiao, Marco Gruteser, and Michael J. Pazzani. 2010. An energy-efficient mobile recommender system. In KDD. Washington DC, USA, 899--908.
17. Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters 12.3 (2001), 211--223.
18. Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations. The Johns Hopkins University Press.
19. D. Gruhl, R. Guha, D. Liben-Nowell, and A. Tomkins. 2004. Information diffusion through blogspace. In WWW ’04. New York, 491--501. www.www2004.org/proceedings/docs/1p491.pdf.
20. Habiba Habiba. 2013. Critical Individuals in Dynamic Population Networks. Ph.D. Dissertation. Northwestern University.
21. Yukio Hayashi, Masato Minoura, and Jun Matsukubo. 2003. Recoverable prevalence in growing scale-free networks and the effective immunization. arXiv:cond-mat/0305549 v2 (Aug. 6 2003).
22. David Heckerman, David Maxwell Chickering, Christopher Meek, Robert Rounthwaite, and Carl Myers Kadie. 2000. Dependency networks for collaborative filtering and data visualization. In UAI. San Francisco, CA, USA, 264--273.
23. Keith Henderson, Brian Gallagher, Lei Li, Leman Akoglu, Tina Eliassi-Rad, Hanghang Tong, and Christos Faloutsos. 2011. It’s who you know: Graph mining using recursive structural features. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, San Diego, CA, USA, 663--671.
24. Herbert W. Hethcote. 2000. The mathematics of infectious diseases. SIAM Rev. 42 (2000), 599--653.
25. Petter Holme, Beom Jun Kim, Chang No Yoon, and Seung Kee Han. 2002. Attack vulnerability of complex networks. Physical Review E 65.5 (2002), 056109.
26. Eitan Israeli and R. Kevin Wood. 2002. Shortest-path network interdiction. Networks 40, 2 (2002), 97--111.
27. U. Kang, Spiros Papadimitriou, Jimeng Sun, and Hanghang Tong. 2011. Centralities in large networks: Algorithms and observations. In SDM. Mesa, AZ, USA, 119--130.
28. Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. Springer, US.
29. George Karypis and Vipin Kumar. 1999. Multilevel -way hypergraph partitioning. In DAC. New Orleans, LA, USA, 343--348.
30. D. Kempe, J. Kleinberg, and E. Tardos. 2003. Maximizing the spread of influence through a social network. In KDD. Washington DC, 137--146.
31. Byung Cho Kim and Sunghwan Jung. 2013. Effective immunization of online networks: A self-similar selection approach. Inf. Tech. Manag. 14, 3 (2013), 257--268.
32. Jon M. Kleinberg. 1998. Authoritative sources in a hyperlinked environment. In ACM-SIAM Symposium on Discrete Algorithms.
33. Yehuda Koren. 2009. Collaborative filtering with temporal dynamics. In KDD. Paris, France, 447--456.
34. Ravi Kumar, Jasmine Novak, Prabhakar Raghavan, and Andrew Tomkins. 2005. On the bursty evolution of blogspace. In WWW. Chiba, Japan, 159--178.
35. Theodoros Lappas, Kun Liu, and Evimaria Terzi. 2009. Finding a team of experts in social networks. In KDD. Paris, France, 467--476.
36. Theodoros Lappas, Evimaria Terzi, Dimitrios Gunopulos, and Heikki Mannila. 2010. Finding effectors in social networks. In KDD. Washington DC, USA, 1059--1068.
37. Jure Leskovec, Lada A. Adamic, and Bernardo A. Huberman. 2006. The dynamics of viral marketing. In EC. ACM Press, New York, NY, USA, 228--237.
38. Jure Leskovec, Mary McGlohon, Christos Faloutsos, Natalie Glance, and Matthew Hurst. 2007. Cascading behavior in large blog graphs: Patterns and a model. In Society of Applied and Industrial Mathematics: Data Mining (SDM07). Mineapolis, MN, USA, 551--556.
39. Weifa Liang, Xiaojun Shen, and Qing Hu. 2000. Finding the most vital edge for graph minimization problems on meshes and hypercubes. International Journal of Parallel and Distributed Systems and Networks 3.4 (2000), 197--205.
40. David Liben-Nowell and Jon Kleinberg. 2007. The link prediction problem for social networks. Journal of the American Society for Information Science and Technology 58.7 (2007), 1019--1031.
41. Ryan Lichtenwalter, Jake T. Lussier, and Nitesh V. Chawla. 2010. New perspectives and methods in link prediction. In KDD. Washington DC, 243--252.
42. Chao Liu, Fan Guo, and Christos Faloutsos. 2009. BBM: Bayesian browsing model from petabyte-scale data. In KDD. Paris, France, 537--546.
43. Arun S. Maiya. 2011. Sampling and Inference in Complex Networks. Ph.D. Dissertation. Stanford University.
44. Arun S. Maiya and Tanya Y. Berger-Wolf. 2010. Sampling community structure. In WWW. Raleigh, NC, USA, 701--710.
45. Arun S. Maiya and Tanya Y. Berger-Wolf. 2011. Benefits of bias: Towards better characterization of network sampling. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, San Diego, 105--113.
46. Jose Marcelino and Marcus Kaiser. 2009. Reducing influenza spreading over the airline network. PLoS Currents 1 (2009).
47. Hossein Maserrat and Jian Pei. 2010. Neighbor query friendly compression of social networks. In KDD. Washington DC, USA, 533--542.
48. Yasuko Matsubara, Yasushi Sakurai, B. Aditya Prakash, Lei Li, and Christos Faloutsos. 2012. Rise and fall patterns of information diffusion: Model and implications. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, Beijing, 6--14.
49. Attilio Milanese, Jie Sun, and Takashi Nishikawa. 2010. Approximating spectral impact of structural perturbations in large networks. Physical Review E 81.4 (2010), 046112.
50. James Moody and Douglas R. White. 2002. Social cohesion and embeddedness: A hierarchical conception of social groups. Sociological Methodology (2002), 365--368.
51. Jennifer Neville, Brian Gallagher, and Tina Eliassi-Rad. 2009. Evaluating statistical tests for within-network classifiers of relational data. In ICDM. Miami, FL, USA, 397--406.
52. M. E. J. Newman. 2005. A measure of betweenness centrality based on random walks. Soc. Networks 27 (2005), 39--54.
53. Huy Nguyen. 2013. Interactions on Complex Networks: Inference Algorithms and Applications. Ph.D. Dissertation. University of Houston.
54. Huy Nguyen and Rong Zheng. 2013. On budgeted influence maximization in social networks. IEEE J. Select. Areas Commun. 31, 6 (2013), 1084--1094.
55. Caleb C. Noble and Diane J. Cook. 2003. Graph-based anomaly detection. In KDD. Washington DC, 631--636.
56. Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1998. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford Digital Library Technologies Project. Retrieved from http://dbpubs.stanford.edu/pub/1999-66 Paper SIDL-WP-1999-0120.
57. Cynthia A. Phillips. 1993. The network inhibition problem. In STOC. San Diego, CA, USA, 776--785.
58. B. Aditya Prakash. 2012a. propagation and immunization in large networks. XRDS: Crossroads, The ACM Magazine for Students 19, 1 (2012), 56--59.
59. B. Aditya Prakash. 2012b. Understanding and Managing Propagation on Large Networks: Theory, Algorithms, and Models. Ph.D. Dissertation. Carnegie Mellon University, Pittsburgh.
60. B. Aditya Prakash, Deepayan Chakrabarti, Michalis Faloutsos, Nicholas Valler, and Christos Faloutsos. 2012a. Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and Information Systems 33.3 (2012), 549--575.
61. B. Aditya Prakash, Hanghang Tong, Nicholas Valler, Michalis Faloutsos, and Christos Faloutsos. 2010. Virus propagation on time-varying networks: Theory and immunization algorithms. In ECML/PKDD (3). Barcelona, Spain, 99--114.
62. B. Aditya Prakash, Jilles Vreeken, and Christos Faloutsos. 2012b. Spotting culprits in epidemics: How many and which ones?. In Data Mining (ICDM), 2012 IEEE 12th International Conference on. IEEE, Brussels, Belgium, 11--20.
63. B. Aditya Prakash, Jilles Vreeken, and Christos Faloutsos. 2013. Efficiently spotting the starting points of an epidemic in a large graph. Knowl. Info. Sys. (2013), 1--25.
64. M. Richardson and P. Domingos. 2002. Mining knowledge-sharing sites for viral marketing. SIGKDD. Edmonton, AB, CA, 61--70.
65. Kazumi Saito, Kouzou Ohara, Yuki Yamagishi, Masahiro Kimura, and Hiroshi Motoda. 2011. Learning diffusion probability based on node attributes in social networks. In Foundations of Intelligent Systems. Springer, 153--162.
66. Venu Satuluri and Srinivasan Parthasarathy. 2009. Scalable graph clustering using stochastic flows: Applications to community discovery. In KDD. Paris, France, 737--746.
67. Christian M. Schneider, Tamara Mihaljev, Shlomo Havlin, and Hans J. Herrmann. 2011. Restraining epidemics by improving immunization strategies. CoRR abs/1102.1929 (2011).
68. Hanhuai Shan and Arindam Banerjee. 2010. Generalized probabilistic matrix factorizations for collaborative filtering. In ICDM. Sydney, Australia, 1025--1030.
69. Hong Shen. 1995. Finding the k most vital edges with respect to minimum spanning tree. Acta Inform. 36 (1995), 405--424.
70. G. W. Stewart and Ji-Guang Sun. 1990. Matrix Perturbation Theory. Academic Press.
71. Chenhao Tan, Jie Tang, Jimeng Sun, Quan Lin, and Fengjiao Wang. 2010. Social action tracking via noise tolerant time-varying factor graphs. In KDD. Washington DC, 1049--1058.
72. Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2012. Gelling, and melting, large graphs by edge manipulation. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management. ACM, Maui, Hawaii, 245--254.
73. Hanghang Tong, B. Aditya Prakash, Charalampos E. Tsourakakis, Tina Eliassi-Rad, Christos Faloutsos, and Duen Horng Chau. 2010. On the vulnerability of large graphs. In ICDM. Sydney, Australia, 1091--1096.
74. Gaurav Tuli, Chris J. Kuhlman, Madhav V. Marathe, S. S. Ravi, and Daniel J. Rosenkrantz. 2012. Blocking complex contagions using community structure. In Workshop Multiagent Interaction Netw.
75. Nicholas Valler, B. Aditya Prakash, Hanghang Tong, Michalis Faloutsos, and Christos Faloutsos. 2011. Epidemic spread in mobile ad hoc networks: Determining the tipping point. In Networking (1). 266--280.
76. Nicholas Charles Valler. 2012. Spreading Processes on Networks Theory and Applications. Ph.D. Dissertation. UNIVERSITY OF CALIFORNIA.
77. Dashun Wang, Zhen Wen, Hanghang Tong, Ching-Yung Lin, Chaoming Song, and Albert-László Barabási. 2011. Information spreading in context. In Proceedings of the 20th International Conference on World Wide Web. ACM, Hyderabad, India, 735--744.
78. Yang Wang, Deepayan Chakrabarti, Chenxi Wang, and Christos Faloutsos. 2003. Epidemic spreading in real networks: An eigenvalue viewpoint. In SRDS. 25--34.
79. Xuetao Wei, Nicholas C. Valler, B. Aditya Prakash, Iulian Neamtiu, Michalis Faloutsos, and Christos Faloutsos. 2013. Competing memes propagation on networks: A network science perspective. Selected Areas in Communications, IEEE Journal on 31, 6 (2013), 1049--1060.
80. R. Kevin Wood. 1993. Network interdiction problem. Math. Com. Model. 17, 2 (1993), 1--18.
81. D. Xin, J. Han, X. Yan, and H. Cheng. 2005. Mining compressed frequent-pattern sets. In VLDB. Trondheim, Norway, 709--720.
82. Yuki Yamagishi, Kazumi Saito, Kouzou Ohara, Masahiro Kimura, and Hiroshi Motoda. 2011. Learning attribute-weighted voter model over social networks. J. Mach. Learn. Res.-Proc. Track 20 (2011), 263--280.
83. Xiaoxin Yin, Jiawei Han, and Philip S. Yu. 2005. Cross-relational clustering with user’s guidance. In KDD. Chicago, IL, USA, 344--353.

Index Terms

• Information systems

  • Information systems applications