Yi-Cheng Chen
Abstract
Given a social graph, the problem of influence maximization is to determine a set of nodes that maximizes the spread of influences. While some recent research has studied the problem of influence maximization, these works are generally too time consuming for practical use in a large-scale social network. In this article, we develop a new framework, community-based influence maximization (CIM), to tackle the influence maximization problem with an emphasis on the time efficiency issue. Our proposed framework, CIM, comprises three phases: (i) community detection, (ii) candidate generation, and (iii) seed selection. Specifically, phase (i) discovers the community structure of the network; phase (ii) uses the information of communities to narrow down the possible seed candidates; and phase (iii) finalizes the seed nodes from the candidate set. By exploiting the properties of the community structures, we are able to avoid overlapped information and thus efficiently select the number of seeds to maximize information spreads. The experimental results on both synthetic and real datasets show that the proposed CIM algorithm significantly outperforms the state-of-the-art algorithms in terms of efficiency and scalability, with almost no compromise of effectiveness.
- R. Albert, H. Jeong, and A. Barabasi. 1999. Diameter of the World Wide Web. Nature 401, 130--131.Google Scholar
Cross Ref
- A. Barabasi and R. Albert. 1999. Emergence of scaling in random networks. Science 286, 509--512.Google ScholarCross Ref
- D. Bortner and J. Han. 2010. Progressive clustering of networks using structure-connected order of traversal. In Proceedings of the 26th IEEE International Conference on Data Engineering (ICDE'10). 653--656.Google Scholar
- Y. Chen, S. Chang, C. Chou, W. Peng, and S. Lee. 2012. Exploring community structures for influence maximization in social networks. In Proceedings of the 6th SNA-KDD Workshop on Social Network Mining and Analysis held in conjunction with KDD'12 (SNA-KDD'12). 1--6.Google Scholar
- W. Chen, Y. Wang, and S. Yang. 2009. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'09). 199--208. Google ScholarDigital Library
- L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas. 2005. Comparing community structure identification. J. Stat. Mech. Theory Exp. 2005, 9.Google ScholarCross Ref
- P. Domingos. 2005. Mining social networks for viral marketing. IEEE Intell. Syst. 20, 1, 80--93.Google ScholarDigital Library
- P. Domingos and M. Richardson. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'01). 57--66. Google ScholarDigital Library
- P. Domingos and M. Richardson. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'02). 61--70. Google ScholarDigital Library
- M. Ester, H. Kriegel, J. Sander, and X. Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96). 226--231.Google Scholar
- P. Estevez, P. Vera, and K. Saito. 2007. Selecting the most influential nodes in social network. In Proceedings of the International Joint Conference on Neural Networks (IJCNN'07). 2397--2402.Google Scholar
- Z. Feng, X. Xu, N. Yuruk, and T. Schweiger. 2007. A novel similarity-based modularity function for graph partitioning. In Proceedings of the 9th International Conference on Data Warehousing and Knowledge Discovery (DaWaK'07). 385--396. Google ScholarDigital Library
- L. Freeman. 1977. A set of measures of centrality based on betweenness. Sociometry 40, 1, 35--41.Google ScholarCross Ref
- M. Girvan and M. Newman. 2002. Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99, 12, 7821--7826.Google ScholarCross Ref
- J. Goldenberg, B. Libai, and E. Muller. 2001. Talk of network: A complex systems look at the underlying process of word-of-mouth. Market. Lett. 12, 3, 211--223.Google ScholarCross Ref
- M. Gomez-Rodrigues, D. Balduzzi, and B. Scholkopf. 2011. Uncovering the temporal dynamics of diffusion networks. In Proceedings of the 28th International Conference on Machine Learning (ICML'11). 561--568.Google Scholar
- M. Gomez-Rodriguez, J. Leskovec, and A. Krause. 2010. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (KDD'10). 1019--1028. Google ScholarDigital Library
- J. Huang, H. Sun, J. Han, H. Deng, Y. Sun, and Y. Liu. 2010. SHRINK: A structural clustering algorithm for detecting hierarchical communities in networks. In Proceedings of the 19th ACM Conference on Information and Knowledge Management (CIKM'10). 219--228. Google ScholarDigital Library
- G. Karypis, and V. Kumar. 1996. Parallel multilevel k-way partitioning scheme for irregular graphs. In Proceedings of the ACM/IEEE Conference on Supercomputing (SC'96). 1--21. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and E. Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03). 137--146. Google ScholarDigital Library
- A. Lancichinetti, S. Fortnato, and J. Keryesz. 2009. Detecting the overlapping and hierarchical community structure in complex network. New J. Physics 11, 3.Google ScholarCross Ref
- A. Lancichinetti, S. Fortnato, and F. Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Phy. Rev. E 78, 4.Google Scholar
- H. Ma, H. Yang, M. Lyu, and I. King. 2008. Mining social networks using heat diffusion processes for marketing candidates selection. In Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM'08). 233--242. Google ScholarDigital Library
- S. Myers and J. Leskovec. 2010. On the convexity of latent social network inference. In Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS'10). 1741--1749.Google Scholar
- A. Ng, M. Jordan, and Y. Weiss. 2001. On spectral clustering: Analysis and an algorithm. In Proceedings of the Conference on Neural Information Processing Systems: Natural and Synthetic (NIPS'01). 849--856.Google Scholar
- M. Newman. 2004. Fast algorithm for detecting community structure in networks. Phy. Rev. E 69, 6.Google Scholar
- M. Newman. 2006. Modularity and community structure in networks. Proc. Nat. Acad. Sci. U.S.A. 103, 23, 8577--8582.Google ScholarCross Ref
- G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435. 814--818.Google Scholar
- E. ROGERS. 2003. Diffusion of Innovations. 5th Ed., Free Press, New York, NY.Google Scholar
- J. Ruan and W. Zhang. 2007. An efficient spectral algorithm for network community discovery and its applications to biological and social networks. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM'07). 643--648. Google ScholarDigital Library
- K. Saito, M. Kimura, K. Ohara, and H. Motoda. 2011. Efficient discovery of influential nodes for SIS models in social networks. Knowl. Inform. Syst. 30, 3, 613--635. Google ScholarDigital Library
- T. Valente. 1995. Network Models of the Diffusion of Innovations. Hampton Press.Google Scholar
- L. Wan, J. Liao, and X. Zhu. 2008. Finding evaluating community structure in social networks. In Proceedings of the 4th International Conference on Advanced Data Mining and Applications (ADMA'08). 620--627. Google ScholarDigital Library
- Y. Wang and X. Feng. 2009. A potential-based node selection strategy for influence maximization in a social network. In Proceedings of the 5th International Conference on Advanced Data Mining and Applications (ADMA'09). 350--361. Google ScholarDigital Library
- S. Wasserman and K. Faust. 1994. Social network analysis: Methods and applications. Cambridge University Press.Google Scholar
- S. White and P. Smyth. 2005. A spectral clustering approach to finding communities in graph. In Proceedings of the 5th SIAM International Conference on Data Mining (SDM'05). 274--286.Google Scholar
- X. Xu, N. Yuruk, Z. Feng, and T. Schweiger. 2007. SCAN: A structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'07). 824--833. Google ScholarDigital Library
- H. Young. 2000. The diffusion of innovations in social networks. Economics Working Paper 437, Johns Hopkins University.Google Scholar
- W. Zachary. 1997. An information flow model for conflict and fission in small group. J. Anthro. Res. 33, 452--473.Google ScholarCross Ref
Index Terms
- CIM: Community-Based Influence Maximization in Social Networks
Recommendations
CFIN: A community-based algorithm for finding influential nodes in complex social networks
AbstractInfluence maximization (IM) problem, a fundamental algorithmic problem, is the problem of selecting a set of k users (refer as seed set) from a social network to maximize the expected number of influenced users (also known as influence spread). ...
Efficient algorithms for influence maximization in social networks
In recent years, due to the surge in popularity of social-networking web sites, considerable interest has arisen regarding influence maximization in social networks. Given a social network structure, the problem of influence maximization is to determine ...
Minimum positive influence dominating set and its application in influence maximization: a learning automata approach
In recent years, with the rapid development of online social networks, an enormous amount of information has been generated and diffused by human interactions through online social networks. The availability of information diffused by users of online ...
Comments