ABSTRACT
When tackling large-scale influence maximization (IM) problem, one effective strategy is to employ graph sparsification as a pre-processing step, by removing a fraction of edges to make original networks become more concise and tractable for the task. In this work, a Cross-Network Graph Sparsification (CNGS) model is proposed to leverage the influence backbone knowledge pre-detected in a source network to predict and remove the edges least likely to contribute to the influence propagation in the target networks. Experimental results demonstrate that conducting graph sparsification by the proposed CNGS model can obtain a good trade-off between efficiency and effectiveness of IM, i.e., existing IM greedy algorithms can run more efficiently, while the loss of influence spread can be made as small as possible in the sparse target networks.
- P. Domingos, and M. Richardson. Mining the network value of customers. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003. Google ScholarDigital Library
- J. Leskovec, A. Krause, and C. Guestrin. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007. Google ScholarDigital Library
- W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009. Google ScholarDigital Library
- A. Goyal, W. Lu, and L. V. S. Lakshmanan. Celf++: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference Companion on World Wide Web, 2011. Google ScholarDigital Library
- B. Wilder, and G. Sukthankar. Sparsification of Social Networks Using Random Walks. In Proceedings of International Conference on Social Computation (SocialCom), 2015.Google Scholar
- M. Mathioudakis, F. Bonchi, and C. Castillo. Sparsification of influence networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011. Google ScholarDigital Library
- F. Zhou, S.Mahler, and H. Toivonen. Simplification of networks by edge pruning. In Bisociative Knowledge Discovery, 2012. Google ScholarCross Ref
- H. Lamba, and R. Narayanam. A novel and model independent approach for efficient influence maximization in social networks. In Proceedings of International Conference on Web Information Systems Engineering, 2013. Google ScholarCross Ref
- Q. Hu, G. Wang, and P. S. Yu. Transferring influence: Supervised learning for efficient influence maximization across networks. In International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), 2014.Google Scholar
- M. Chen, K. Q. Weinberger, and J. Blitzer. Co-training for domain adaptation. In Advances in Neural Information Processing Systems, 2011.Google Scholar
Index Terms
- Leveraging Cross-Network Information for Graph Sparsification in Influence Maximization
Recommendations
Local graph sparsification for scalable clustering
SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of dataIn this paper we look at how to sparsify a graph i.e. how to reduce the edgeset while keeping the nodes intact, so as to enable faster graph clustering without sacrificing quality. The main idea behind our approach is to preferentially retain the edges ...
SGCN: A Graph Sparsifier Based on Graph Convolutional Networks
Advances in Knowledge Discovery and Data MiningAbstractGraphs are ubiquitous across the globe and within science and engineering. With graphs growing in size, node classification on large graphs can be space and time consuming, even with powerful classifiers such as Graph Convolutional Networks (GCNs)...
Efficient location-aware influence maximization
SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Datausers in a social network to maximize the expected number of users influenced by the selected users (called influence spread), has been extensively studied, existing works neglected the fact that the location information can play an important role in ...
Comments