Skip to main content
SpringerLink
Log in

Influence maximization in online social network using different centrality measures as seed node of information propagation

  • Published:
Sādhanā Aims and scope Submit manuscript

Abstract

Information propagation in the network is probabilistic in nature; simultaneously, it depends on the connecting paths of the propagation. Selection of seed nodes plays an important role in determining the levels and depth of the contagion in the network. This paper presents a comparative study when seed nodes for information propagation are selected through the properties of different centrality measures in the social network. This study captures the interaction measures of nodes in the social network, selects seed nodes based on five centrality measures, i.e. degree distribution, betweenness centrality, closeness centrality, Eigenvector and PageRank, and compares the affected nodes and levels of propagation within the network. We demonstrate the performance of the different centrality measures by processing three datasets of social network: Twitter network, Bitcoin network and author collaborative network. For the propagation of the information, we use breadth-first search (BFS) and susceptible–infectious–recovered (SIR) model and a detailed comparative study is also presented for each of the seed nodes selected using aforementioned network properties. Results show that the Eigenvector centrality and PageRank centrality measures outperform other centrality measures in all test cases in terms of propagation level and affected nodes during information propagation. Both Eigenvector and PageRank network data processing required a high computational overhead. For this reason we propose a hybrid model where using k-core the network is degenerated into a smaller network and centrality nodes are extracted from the smaller network. These centrality nodes, as compared to original centrality nodes, perform almost in the same manner in terms of influence maximization when k is chosen in a rational way.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Figure 16

Similar content being viewed by others

References

  1. Tripathy R M, Bagchi A and Mehta S 2010 A study of rumor control strategies on social networks. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10, ACM, pp. 1817–1820

  2. Grando F, Noble D and Lamb L C 2016 An analysis of centrality measures for complex and social networks. In: Proceedings of the IEEE Global Communications Conference (GLOBECOM), Washington, DC, pp. 1–6

  3. Leskovec J, Adamic L A and Huberman B A 2006 The dynamics of viral marketing. In: Proceedings of the ACM Conference on Electronic Commerce, pp. 228–237

  4. Vicario M D, Zollo F, Caldarelli G and Scala A and Quattrociocchi W 2017 Mapping social dynamics on Facebook: the Brexit debate. Social Networks 50: 6–16

    Article  Google Scholar 

  5. Li X, Rao Y, Xie H, Liu X, Wong T and Wang F L 2017 Social emotion classification based on noise-aware training. Data & Knowledge Engineering. https://doi.org/10.1016/j.datak.2017.07.008

    Article  Google Scholar 

  6. Amplayo R K and Song M 2017 Adaptable fine-grained sentiment analysis for summarization of multiple short online reviews. Data & Knowledge Engineering 110: 54–67

    Article  Google Scholar 

  7. Vavliakis K N, Symeonidis A L and Mitkas P A 2013 Event identification in web social media through named entity recognition and topic modeling. Data & Knowledge Engineering 88: 1–24

    Article  Google Scholar 

  8. Reyes A, Rosso P and Buscaldi D 2012 From humor recognition to irony detection: the figurative language of social media. Data & Knowledge Engineering 74: 1–12

    Article  Google Scholar 

  9. Zaharia M, Chowdhury M, Franklin M J, Shenker S and Stoica I 2010. In: Proceedings of HotCloud

  10. Apache Spark. http://spark.apache.org/

  11. Mendoza M, Poblete B and Castillo C 2010 Twitter under crisis: can we trust what we get? In: Proceedings of the First Workshop on Social Media Analytics, pp. 71–79

  12. Yang B, Di J, Liu J and Liu D 2013 Hierarchical community detection with applications to real-world network analysis. Data & Knowledge Engineering 83: 20–38

    Article  Google Scholar 

  13. Shi C, Cai Y, Fu D, Dong Y and Wu B 2013 A link clustering based overlapping community detection algorithm. Data & Knowledge Engineering 87: 394–404

    Article  Google Scholar 

  14. Holthoefer J B and Moreno Y 2012 Absence of influential spreaders in rumor dynamics. Physical Review E 85: 026116

    Article  Google Scholar 

  15. Arruda G F, Barbieri A L, Rodriguez P M, Rodrigues F A, Moreno Y and Costa L F 2014 The role of centrality for the identification of influential spreaders in complex networks. Physical Review E 90(3): 032812–032829

    Article  Google Scholar 

  16. Miritello G, Moro E and Lara R 2010 The dynamical strength of social ties in information spreading. Physics Review E 83: 045102

    Article  Google Scholar 

  17. Wenjing Y, Brenner L and Giua A 2019 Influence maximization in independent cascade networks based on activation probability computation. IEEE Access PP(99): 1. https://doi.org/10.1109/ACCESS.2019.2894073

    Article  Google Scholar 

  18. Kempe D, Kleinberg J and Tardos E 2003 Maximizing the spread of influence in a social network. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 137–146

  19. Sun J and Tang J 2011 A survey of models and algorithms for social influence analysis. Social network data analytics. Springer, Boston, MA, pp. 177–214

    Chapter  Google Scholar 

  20. Yao Q, Shi R, Zhou C, Wang P and Guo L 2015 Topic-aware social influence minimization. In: Proceedings of the 24th International Conference on World Wide Web Companion, International World Wide Web Conferences Steering Committee, pp. 139–140

  21. Dey P and Roy S 2016 Social network analysis. In: Advanced Methods for Complex Network Analysis. IGI, Hershey, Pennsylvania, USA, pp. 237–265

    Google Scholar 

  22. Guzman J D, Deckro R F, Robbins M J, Morris J F and Ballester N A 2014 An analytical comparison of social network measures. IEEE Transactions on Computational Social Systems 1(1): 35–45

    Article  Google Scholar 

  23. Page L, Brin S, Motwani R and Winograd T 1999 The PageRank citation ranking: bringing order to the web. Tech. Report, Stanford InfoLab

  24. Jiang J, Wen S, Liu B, Yu S, Xiang Y and Zhou W 2019 Identifying propagation source in time-varying networks. Malicious attack propagation and source identification. Cham: Springer, pp. 117–137

    Google Scholar 

  25. Domenico M D, Lima A, Mougel P and Musolesi M 2013 The anatomy of a scientific rumor. (Nature Open Access) Scientific Reports 3: 2980

    Google Scholar 

  26. Newman M E J 2004 Coauthorship networks and patterns of scientific collaboration. In: Proceedings of the National Academy of Science, pp. 5200–5205

    Article  Google Scholar 

  27. Kumar S, Spezzano F, Subrahmanian VS and Faloutsos C 2016 Edge weight prediction in weighted signed networks. In: Proceedings of the IEEE International Conference on Data Mining, ICDM

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Jadavpur University, Kolkata, India

    Paramita Dey, Agneet Chaterjee & Sarbani Roy

Authors
  1. Paramita Dey
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Agneet Chaterjee
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sarbani Roy
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sarbani Roy.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dey, P., Chaterjee, A. & Roy, S. Influence maximization in online social network using different centrality measures as seed node of information propagation. Sādhanā 44, 205 (2019). https://doi.org/10.1007/s12046-019-1189-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s12046-019-1189-7

Keywords

Search

Navigation