›› 2015, Vol. 30 ›› Issue (1): 184-199.doi: 10.1007/s11390-015-1512-7

Special Issue: Surveys; Data Management and Data Mining

• Data Management and Data Mining • Previous Articles     Next Articles

Social Influence Study in Online Networks: A Three-Level Review

Hui Li(李辉), Member, CCF, ACM, Jiang-Tao Cui(崔江涛), Member, CCF, ACM, Jian-Feng Ma(马建峰), Member, CCF, IEEE   

  1. School of Cyber Engineering, Xidian University, Xi'an 710126, China
  • Received:2014-01-10 Revised:2014-04-25 Online:2015-01-05 Published:2015-01-05
  • About author:Hui Li received his B.E. degree from Harbin Institute of Technology in 2005 and Ph.D. degree in computer engineering from Nanyang Techno- logical University, Singapore, in July 2012. He is an Associate Professor in the School of Cyber Engineering, Xidian University, Xi'an. His research interests include data mining, knowledge management and discovery, privacy-preserving query and analysis in big data. He is a member of CCF and ACM.
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61173089, 61202179, 61472298, and U1135002, the Scientific Research Foundation for the Returned Overseas Chinese Scholars of State Education Ministry of China, and the Fundamental Research Funds for the Central Universities of China.

Social network analysis (SNA) views social relationships in terms of network theory consisting of nodes and ties. Nodes are the individual actors within the networks; ties are the relationships between the actors. In the sequel, we will use the term node and individual interchangeably. The relationship could be friendship, communication, trust, etc. These reason is that these relationships and ties are driven by social in uence, which is the most important phenomenon that distinguishes social network from other networks. In this paper, we present an overview of the representative research work in social in uence study. Those studies can be classi ed into three levels, namely individual, community, and network levels. Throughout the study, we are able to unveil a series of research directions in future and possible applications based on the state-of-the-art study.

[1] Brown J, Reingen P. Social ties and word-of-mouth referral behavior. The Journal of Consumer Research, 1987, 14(3): 350-362.

[2] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions. Math. Programming, 1978, 14(1): 265-294.

[3] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In Proc. the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2003, pp. 137-146.

[4] Cha M, Antonio J, Pérez N, Haddadi H. Flash floods and ripples: The spread of media content through the blogosphere. In Proc. the 3rd International AAAI Conference on Weblogs and Social Media, May 2009, pp. 8-15.

[5] Herlocker J L, Konstan J A, Terveen L G, Riedl J T. Evaluating collaborative filtering recommender systems. ACM Trans. Inf. Syst., 2004, 22(1): 5-53.

[6] Koren Y. Factor in the neighbors: Scalable and accurate collaborative filtering. ACM Trans. Knowl. Discov. Data, 2010, 4(1): Article No. 1.

[7] Leskovec J, Adamic L A, Huberman B A. The dynamics of viral marketing. In Proc. the 7th ACM Conference on Electronic Commerce, Jun. 2006, pp. 228-237.

[8] Liu Y, Huang X, An A, Yu X. ARSA: A sentiment-aware model for predicting sales performance using blogs. In Proc. the 30th International ACM SIGIR Conference on Research and Development in Information Retrieval, July 2007, pp. 607-614.

[9] Rogers E M. Diffusion of Innovations (5th edition). New York: Free Press, 2003.

[10] Bakshy E, Hofman J M, Mason W A, Watts D J. Everyone's an influencer: Quantifying influence on twitter. In Proc. the 4th ACM International Conference on Web Search and Data Mining, Feb. 2011, pp 65-74.

[11] Bao H, Chang E Y. AdHeat: An influence-based diffusion model for propagating hints to match ads. In Proc. the 19th International Conference on World Wide Web, Apr. 2010, pp. 71-80.

[12] Borgatti SP. The key player problem. In Dynamic Social Network Modeling and Analysis: 2002 Workshop Summary and Papers, Breiger R, Carley K M, Pattison P(eds.), Washington, DC: National Academies Press, 2004, pp.241-252.

[13] Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J M, Glance N S. Cost-effective outbreak detection in networks. In Proc. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2007, pp. 420-429.

[14] Agarwal N, Liu H, Tang L, Yu P S. Identifying the influential bloggers in a community. In Proc. the 1st ACM International Conference on Web Search and Data Mining, Feb. 2008, pp. 207-218.

[15] Ma H, Yang H, Lyu M R, King I. Mining social networks using heat diffusion processes for marketing candidates selection. In Proc. the 17th ACM International Conference on Information and Knowledge Management, Oct. 2008, pp. 233-242.

[16] Pal A, Counts S. Identifying topical authorities in microblogs. In Proc. the 4th ACM International Conference on Web Search and Data Mining, Feb. 2011, pp. 45-54.

[17] Li H, Bhowmick S S, Sun A. Casino: Towards conformityaware social influence analysis in online social networks. In Proc. the 20th ACM International Conference on Information and Knowledge Management, Oct. 2011, pp. 1007-1012.

[18] Liben-Nowell D, Kleinberg J. The link prediction problem for social networks. In Proc. the 12th ACM International Conference on Information and Knowledge Management, Nov. 2003, pp. 556-559.

[19] Newman M E. Clustering and preferential attachment in growing networks. Physical Review E, 2001, 64(2): 025102.

[20] Albert R, Barabási A L. Topology of evolving networks: Local events and universality. Physical Review Letters, 2000, 85(24): 5234-5237.

[21] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509-512.

[22] O'Madadhain J, Hutchins J, Smyth P. Prediction and ranking algorithms for event-based network data. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 23-30.

[23] Leskovec J, Huttenlocher D, Kleinberg J. Predicting positive and negative links in online social networks. In Proc. the 19th International Conference on World Wide Web, Apr. 2010, pp. 641-650.

[24] Cai K, Bao S, Yang Z, Tang J, Ma R, Zhang L, Su Z. OOLAM: An opinion oriented link analysis model for influence persona discovery. In Proc. the 4th ACM International Conference on Web Search and Data Mining, Feb. 2011, pp. 645-654.

[25] Li H, Bhowmick S S, Sun A, Cui J. Affinity-driven blog cascade analysis and prediction. Data Mining and Knowledge Discovery, 2014, 28(2): 442-474.

[26] Li H, Bhowmick S S, Sun A. Blog cascade affinity: Analysis and prediction. In Proc. the 18th ACM International Conference on Information and Knowledge Management, Nov. 2009, pp. 1117-1126.

[27] Chin A, Chignell M H. A social hypertext model for finding community in blogs. In Proc. the 17th ACM Conference on Hypertext and Hypermedia, Aug. 2006, pp. 11-22.

[28] Xu X, Yuruk N, Feng Z, Schweiger T A J. SCAN: A structural clustering algorithm for networks. In Proc. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2007, pp. 824-833.

[29] Jo Y, Lagoze C, Giles C L. Detecting research topics via the correlation between graphs and texts. In Proc. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2007, pp. 370-379.

[30] Kumar R, Novak J, Raghavan P, Tomkins A. On the bursty evolution of blogspace. In Proc. the 12th International Conference on World Wide Web, May 2003, pp. 568-576.

[31] Backstrom L, Huttenlocher D, Kleinberg J, Lan X. Group formation in large social networks: Membership, growth, and evolution. In Proc. the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2006, pp. 44-54.

[32] Lin Y, Chi Y, Zhu S, Sundaram H, Tseng B L. Analyzing communities and their evolutions in dynamic social networks. ACM Trans. Knowl. Discov. Data, 2009, 3(2): Article No. 8.

[33] Lin Y, Sundaram H, Chi Y, Tatemura J, Tseng B L. Blog community discovery and evolution based on mutual awareness expansion. In Proc. IEEE/WIC/ACM International Conference on Web Intelligence, Nov. 2007, pp. 48-56.

[34] Sun J, Faloutsos C, Papadimitriou S, Yu P S. Graphscope: Parameter-free mining of large time-evolving graphs. In Proc. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2007, pp. 687-696.

[35] Spiliopoulou M, Ntoutsi I, Theodoridis Y, Schult R. Monic: Modeling and monitoring cluster transitions. In Proc. the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2006, pp. 706-711.

[36] Bansal N, Chiang F, Koudas N, Tompa F W. Seeking stable clusters in the blogosphere. In Proc. the 33rd International Conference on Very Large Data Bases, Sept. 2007, pp. 806-817.

[37] Asur S, Parthasarathy S, Ucar D. An event-based framework for characterizing the evolutionary behavior of interaction graphs. In Proc. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2007, pp. 913-921.

[38] Asur S, Parthasarathy S, Ucar D. An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Trans. Knowl. Discov. Data, 2009, 3(4): Article No. 16.

[39] Li H, Bhowmick S S, Sun A. Affinity-driven prediction and ranking of products in online product review sites. In Proc. the 19th ACM International Conference on Information and Knowledge Management, Oct. 2010, pp. 1745-1748.

[40] Li H, Bhowmick S S, Sun A. Affrank: Affinity-driven ranking of products in online social rating networks. Journal of the American Society for Information Science and Technology, 2011, 62(7): 1345-1359.

[41] Leskovec J, Adamic L A, Huberman B A. The dynamics of viral marketing. ACM Trans. Web, 2007, 1(1): Article No. 5.

[42] Cha M, Mislove A, Gummadi K P. A measurement-driven analysis of information propagation in the flickr social network. In Proc. the 18th International Conference on World Wide Web, April 2009, pp. 721-730.

[43] Iribarren J L, Moro E. Information diffusion epidemics in social networks. CoRR, 2007. http://arxiv.org/abs/0706.0641, Dec. 2014.

[44] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks. In Proc. the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jun. 2009, pp. 199-208.

[45] Wang Y, Cong G, Song G, Xie K. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proc. the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jul. 2010, pp. 1039-1048.

[46] Li H, Bhowmick S S, Sun A. Cinema: Conformity-aware greedy algorithm for influence maximization in online social networks. In Proc. the 16th International Conference on Extending Database Technology, Mar. 2013, pp. 323-334.

[47] Kim J, Kim S, Yu H. Scalable and parallelizable processing of influence maximization for large-scale social networks? In Proc. the 29th IEEE International Conference on Data Engineering, Apr. 2013, pp. 266-277.

[48] Jiang Q, Song G, Cong G, Wang Y, Si W, Xie K. Simulated annealing based influence maximization in social networks. In Proc. the 25th AAAI Conference on Arti cial Intelligence, Aug. 2011, pp. 127-132.

[49] Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proc. the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jul. 2010, pp. 1029-1038.

[50] Chen W, Collins A, Cummings R, Ke T, Liu Z, Rinc′on D, Sun X, Wang Y, Wei W, Yuan Y. Influence maximization in social networks when negative opinions may emerge and propagate. In Proc. the 11th SIAM International Conference on Data Mining, Apr. 2011, pp. 379-390.

[51] Chen W, Yuan Y, Zhang L. Scalable influence maximization in social networks under the linear threshold model. In Proc. the 10th IEEE International Conference on Data Mining, Dec. 2010, pp. 88-97.

[52] Goyal A, Lu W, Lakshmanan L V S. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In Proc. the 11th IEEE International Conference on Data Mining, Dec. 2011, pp. 211-220.

[53] Domingos P, Richardson M. Mining the network value of customers. In Proc. the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2001, pp. 57-66.

[54] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing. In Proc. the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jul. 2002, pp. 61-70.

[55] Nemhauser G L, Wolsey L A. Maximizing submodular set functions: Formulations and analysis of algorithms. Studies on Graphs and Discrete Programming, 1981, 11: 279-301.

[56] Iwata S. A fully combinatorial algorithm for submodular function minimization. In Proc. the 13th ACM-SIAM Symposium on Discrete Algorithms, Jan. 2002, pp. 915-919.

[57] Iwata S, Orlin J B. A simple combinatorial algorithm for submodular function minimization. In Proc. the 20th ACMSIAM Symposium on Discrete Algorithms, Jan. 2009, pp. 1230-1237.

[58] Feige U, Mirrokni V S, Vondrak J. Maximizing nonmonotone submodular functions. In Proc. the 48th Annual IEEE Symposium on Foundations of Computer Science, Oct. 2007, pp. 461-471.

[59] Goyal A, Bonchi F, Lakshmanan L V S. A data-based approach to social influence maximization. Proc. the VLDB Endowment, 2011, 5(1): 73-84.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhou Chaochen; Liu Xinxin;. Denote CSP with Temporal Formulas[J]. , 1990, 5(1): 17 -23 .
[2] QI Yuesheng; WANG Baozhong; KANG Lishan;. Genetic Programming with Simple Loops[J]. , 1999, 14(4): 429 -433 .
[3] PENG wei; LU Xicheng;. An Approach to Support IP Multicasting in Networks with Mobile Hosts[J]. , 1999, 14(6): 529 -538 .
[4] Chiou-Yng Lee, Yung-Hui Chen, Che-Wun Chiou, and Jim-Min Lin. Unified Parallel Systolic Multiplier Over GF(2^m)[J]. , 2007, 22(1): 28 -38 .
[5] Yong-Xi Gong, Yu Liu, Lun Wu, and Yu-Bo Xie. Boolean Operations on Conic Polygons[J]. , 2009, 24(3): 568 -577 .
[6] Ji Wang (王戟), Senior Member, CCF, Member, IEEE, Rui Shen (沈锐), Student Member,IEEE and Huai-Min Wang (王怀民), Senior Member, CCF, Member, IEEE. A Programming Language Approach to Internet-Based Virtual Computing Environment[J]. , 2011, 26(4): 600 -615 .
[7] Dong Wang, Member, IEEE, Javier Tejedor, Simon King, Senior Member, IEEE and Joe Frankel, Member, IEEE. Term-Dependent Confidence Normalisation for Out-of-Vocabulary Spoken Term Detection[J]. , 2012, (2): 358 -375 .
[8] Mathu Soothana S. Kumar Retna Swami and Muneeswaran Karuppiah. Optimal Feature Extraction Using Greedy Approach for Random Image Components and Subspace Approach in Face Recognition[J]. , 2013, 28(2): 322 -328 .
[9] Li-Feng He, Yu-Yan Chao, and Kenji Suzuki. An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing[J]. , 2013, 28(3): 468 -478 .
[10] Liang-Jun Zang, Cong Cao, Ya-Nan Cao, Yu-Ming Wu, and Cun-Gen Cao. A Survey of Commonsense Knowledge Acquisition[J]. , 2013, 28(4): 689 -719 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved