A Novel Community-Based Approach for Influence Maximization in Social Network

(*) Corresponding author

Authors' affiliations

DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)


Our study concerns an important current problem, that of influence maximization in social network. This problem has received significant attention from the researchers recently, driven by many potential applications such as viral marketing and sales promotion. It is a fundamental issue to find a subset of key individuals in a social network such that targeting them initially (e.g. to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). However, the problem of finding the most key nodes is unfortunately NP-hard. It has been shown that a greedy algorithm with provable approximation guarantees can give good approximation. However, it is computationally expensive, if not prohibitive, to run the greedy algorithm on a large social network. Based on the community structure property of social network, a cooperative game theoretic algorithm CGINA to find key nodes is proposed. The proposed algorithm encompasses two stages. Firstly, we detect the community structure of the social network with the topological structure and information diffusion model. In this paper, we adopt the algorithm 2 in [4]. Then, we will find key nodes in communities. In this paper, we think of the information diffusion in the whole network as a cooperative game with transferable utility. The communities of the network happen to be the players in this cooperative game. With the solution concept Shapley value in game theory, we allocate the number of key nodes to discover in the community. Moreover, different from the existing relevant literature, in my opinion, the key nodes two parts. One is composed of “bridge” nodes, which contact other communities densely, and are easy to disseminate information across communities, the other is composed of  “influential” nodes, which are at the core of the community, in close touch with other nodes, and can diffuse information quickly within the community. To adjust the ratio of these two kinds of nodes in the same community, a heuristic factor l is introduced. Empirical studies on a large social network show that our algorithm is efficient and powerful.
Copyright © 2013 Praise Worthy Prize - All rights reserved.


Cooperation Game; Influence Maximization; Shapley Value

Full Text:



D. Kempel, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network , Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining(Page: 137 Year of Publication: 2003 ISBN: 1-58113-737-0).

W. Chen, Y. Wang, S. Yang, Efficient influence maximization in social networks, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining(Page: 199 Year of Publication: 2009 ISBN: 978-1-60558-495-9).

J. Leskovec, A. Krause, C. Guestrin, C. Faloustos, J. VanBriesen, N. S. Glance, Cost-effective outbreak detection in networks , Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining(Page: 420 Year of Publication: 2007 ISBN: 978-1-59593-609-7).

Yu Wang,Gao Cong,Guojie Song, Kunqing Xie, Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks, Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining(Page: 1039 Year of Publication: 2010 ISBN: 978-1-4503-0055-1).

U.N.Raghavan, R.Albert, S. Kumara, Near linear time algorithm to detect community structure in large scale-free networks, Physical Review E. Vol.76,n.3,pp. 036106.1-036106.11,2007.

R. Narayanam, Y. Narahari, A Shapley Value Based Approach to Discover Influential Nodes in Social Networks, IEEE Transactions on Automation Science and Engineering. Vol.8, no.1, pp.130-147, 2011.

P. Domingos, M. Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining(Page:57 Year of Publication: 2001 ISBN: 1-58113-391-X).

J. Scripps, P. N. Tan, and A. H. Esfahanian, Exploration of link structure and community-based node roles in network analysis, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining(Page:649 Year of Publication:2007 ISBN: 0-7695-3018-4).

J. Scripps, P.N.Tan, and A. H. Esfahanian, Node roles and community structure in network, Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis(Page:26 Year of Publication:2007 ISBN: 0-7695-3018-4.

A Lancichinetti, S Fortunato, F Radicchi, Benchmark graphs for testing community detection algorithms, Physical Review E. Vol.78,n.4,pp. 046110-046114 ,2008.

Deng, Y., Xu, X., Space-time model of information diffusion from network perspective, (2012) International Review on Computers and Software (IRECOS), 7 (3), pp. 1167-1173

Liu, Z., Zhao, J., Yu, J., Quantity effectiveness analysis of information diffusion based on network dimension-force, (2012) International Review on Computers and Software (IRECOS), 7 (1), pp. 307-313.


  • There are currently no refbacks.

Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize