Influence maximization in complex social networks based on community structure

Document Type : Research Paper

Authors

School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

Many real-world networks, including biological networks, internet, information and social networks can be modeled by a complex network consisting of a large number of elements connected to each other. One of the important issues in complex networks is the evaluation of node importance because of its wide usage and great theoretical significance, such as in information diffusion, control of disease spreading, viral marketing and rumor dynamics. A fundamental issue is to identify a set of most influential individuals who would maximize the influence spread of the network. In this paper, we propose a novel algorithm for identifying influential nodes in complex networks with community structure without having to determine the number of seed nodes based on genetic algorithm. The proposed algorithm can identify influential nodes with three methods at each stage (degree centrality, random and structural hole) in each community and measure the spread of influence again at each stage. This process continues until the end of the genetic algorithm, and at the last stage, the most influential nodes are identified with maximum diffusion in each community. Our community-based influencers detection approach enables us to find more influential nodes than those suggested by page-rank and other centrality measures. Furthermore, the proposed algorithm does not require determining the number of k initial active nodes.

Keywords

Main Subjects

References

Ahajjam, S. and Badir, H. (2018) ‘Identification of influential spreaders in complex networks using HybridRank algorithm’, Scientific Reports. Springer US, (July), pp. 1–10. doi: 10.1038/s41598-018-30310-2.
Azaouzi, M. and Romdhane, L. Ben (2018) ‘An Efficient Two-Phase Model for Computing Influential Nodes in Social Networks Using Social Actions’, 33(2), pp. 286–304. doi: 10.1007/s11390-018-1820-9.
B, S. S. S. et al. (2019) CoIM : Community-Based Influence Maximization in Social Networks. Springer Singapore. doi: 10.1007/978-981-13-3143-5.
Bao, Z. K. et al. (2017) ‘Identification of influential nodes in complex networks: Method from spreading probability viewpoint’, Physica A: Statistical Mechanics and its Applications, 468, pp. 391–397. doi: 10.1016/j.physa.2016.10.086.
Bian, T. and Deng, Y. (2017) ‘A new evidential methodology of identifying influential nodes in complex networks’, Chaos, Solitons and Fractals. Elsevier Ltd, 103, pp. 101–110. doi: 10.1016/j.chaos.2017.05.040.
Burt, R. (1992) Structural holes: the social structure of of competition. Harvard University Press. Available at: https://books.google.com/books/about/Structural_Holes.html?id=FAhiz9FWDzMC (Accessed: 20 January 2018).
Cai, D. et al. (2017) ‘A new method for identifying influential nodes based on D-S evidence theory’, in Proceedings of the 29th Chinese Control and Decision Conference, CCDC 2017, pp. 4603–4609. doi: 10.1109/CCDC.2017.7979310.
D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten,  and S. M. D. (2003) ‘The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations Behav. Ecol. and Sociobiol., 54:396–405’.
Danon, P. M. G. and L. (2003) ‘Community structure in jazz. Advances in Complex Systems Advances in Complex Systems, 6(4):565–573’.
Fei, L. et al. (2017) ‘A new method to identify influential nodes based on combining of existing centrality measures’, Modern Physics Letters B, 175024317. doi: 10.1142/S0217984917502438.
Goldenberg, J. et al. (no date) ‘Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular’, search.proquest.com. Available at: http://search.proquest.com/openview/613a0da9fb3ec5e34ca37c07f8585e77/1?pq-origsite=gscholar&cbl=25818 (Accessed: 28 January 2018).
Gong, M. et al. (2016) ‘Influence maximization in social networks based on discrete particle swarm optimization’, Information Sciences. Elsevier, 367–368, pp. 600–614. doi: 10.1016/j.ins.2016.07.012.
Goyal, A., Lu, W. and Lakshmanan, L. V. S. (2011) ‘CELF++’, in Proceedings of the 20th international conference companion on World wide web - WWW ’11, p. 47. doi: 10.1145/1963192.1963217.
Halappanavar, M., Sathanur, A. V and Nandi, A. K. (2016) ‘Accelerating the mining of influential nodes in complex networks through community detection’, in Proceedings of the ACM International Conference on Computing Frontiers - CF ’16, pp. 64–71. doi: 10.1145/2903150.2903181.
Handl, J. (2007) ‘An evolutionary approach to multiobjective clustering’, ieeexplore.ieee.org. Available at: http://ieeexplore.ieee.org/abstract/document/4079614/ (Accessed: 27 January 2018).
He, J. S., Kaur, H. and Talluri, M. (2016) ‘Positive opinion influential node set selection for social networks: Considering both positive and negative relationships’, in Lecture Notes in Electrical Engineering, pp. 935–948. doi: 10.1007/978-81-322-2580-5_85.
Hosseini-Pozveh, M., Zamanifar, K. and Naghsh-Nilchi, A. R. (2017) ‘A community-based approach to identify the most influential nodes in social networks’, Journal of Information Science, 43(2), pp. 204–220. doi: 10.1177/0165551515621005.
Hu, P. and Mei, T. (2018) ‘Ranking influential nodes in complex networks with structural holes’, Physica A: Statistical Mechanics and its Applications. Elsevier B.V., 490, pp. 624–631. doi: 10.1016/j.physa.2017.08.049.
Huang, H. et al. (2019) ‘Community-based influence maximization for viral marketing’. Applied Intelligence, pp. 9–12.
Jaouadi, M. and Ben Romdhane, L. (2017) ‘DIN: An efficient algorithm for detecting influential nodes in social graphs using network structure and attributes’, in Proceedings of IEEE/ACS International Conference on Computer Systems and Applications, AICCSA. doi: 10.1109/AICCSA.2016.7945698.
Kaur, H., Talluri, M. and He, J. S. (2015) ‘Blocking negative influential node set in social networks: From host perspective’, in 2015 International Conference on Collaboration Technologies and Systems, CTS 2015, pp. 472–473. doi: 10.1109/CTS.2015.7210470.
Kempe, D. and Kleinberg, J. (2003) ‘Maximizing the Spread of Influence through a Social Network Categories and Subject Descriptors’, Science. New York, New York, USA: ACM Press, pages, pp. 137–146. doi: 10.1145/956750.956769.
Leskovec, J. et al. (2007) ‘Cost-effective Outbreak Detection in Networks’.
Liu, D., Jing, Y. and Chang, B. (2016) ‘Identifying influential nodes in complex networks based on expansion factor’, International Journal of Modern Physics C. IEEE, 27(9), p. 1650105. doi: 10.1142/S0129183116501059.
Liu, S. et al. (2015) ‘Identifying effective influencers based on trust for electronic word-of-mouth marketing: A domain-aware approach’, Information Sciences. Elsevier, 306, pp. 34–52. doi: 10.1016/j.ins.2015.01.034.
Newman,  ichelle G. and M. E. J. (2002) ‘Community structure in social and biological networks Proc. Natl. Acad. Sci. U.S.A., 99(12):7821–7826’.
Park, YoungJa,  and M. S. (1998) ‘A genetic algorithm for clustering problems’.
Pei, S. et al. (2016) ‘Searching for superspreaders of information in real- world social media’, nature.com, pp. 1–34. doi: 10.1038/srep05547.
R. Guimera, L. Danon, A. Diaz-Guilera, F. G. and A. A. (2003) ‘Physical Review E’.
Reihanian, A., Feizi-Derakhshi, M. R. and Aghdasi, H. S. (2017) ‘Community detection in social networks with node attributes based on multi-objective biogeography based optimization’, Engineering Applications of Artificial Intelligence. Pergamon, 62, pp. 51–67. doi: 10.1016/j.engappai.2017.03.007.
Scripps, J. (2013) ‘Discovering Influential Nodes in Social Networks through Community Finding.’, WEBIST. Available at: https://pdfs.semanticscholar.org/fe1a/e2b2854e66c8e70eb32c0a6c08b9869e25e2.pdf (Accessed: 19 January 2018).
Shang, J. et al. (2017) ‘CoFIM: A community-based framework for influence maximization on large-scale networks’, Knowledge-Based Systems. Elsevier B.V., 117, pp. 88–100. doi: 10.1016/j.knosys.2016.09.029.
Singh, S. S. et al. (2019) ‘C2IM : Community based context-aware influence maximization in social networks’, Physica A. Elsevier B.V., 514, pp. 796–818. doi: 10.1016/j.physa.2018.09.142.
Song, G. et al. (2017) ‘Influential Node Tracking on Dynamic Social Network: An Interchange Greedy Approach’, IEEE Transactions on Knowledge and Data Engineering, 29(2), pp. 359–372. doi: 10.1109/TKDE.2016.2620141.
Ullah, F. and Lee, S. (2017) ‘Identification of influential nodes based on temporal-aware modeling of multi-hop neighbor interactions for influence spread maximization’, Physica A: Statistical Mechanics and its Applications, 486, pp. 968–985. doi: 10.1016/j.physa.2017.05.089.
Walker, S. K. (2011) ‘Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives’, Journal of Family Theory & Review, 3(3), pp. 220–224. doi: 10.1111/j.1756-2589.2011.00097.x.
Wang, Y. et al. (2010) ‘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 - KDD ’10, p. 1039. doi: 10.1145/1835804.1835935.
Watts, D. (2002) ‘A simple model of global cascades on random networks’, National Acad Sciences. Available at: http://www.pnas.org/content/99/9/5766.short (Accessed: 28 January 2018).
Wei Li and Jianbin Huang (2015) ‘Mining top- k influential nodes in social networks via community detection Wei Li and Jianbin Huang * Shuzhen Wang’, 14, pp. 172–184.
Wenfeng Kang, Guangming Tang, Yifeng Sun, S. W. (2017) ‘Identifying Influential Nodes in Complex Networks Based on Weighted Formal Concept Analysis’, IEEE Access, 5, pp. 3777–3789. doi: 10.1109/ACCESS.2017.2679038.
YEH, J. and LIN, W. (2007) ‘Using simulation technique and genetic algorithm to improve the quality care of a hospital emergency department’, Expert Systems with Applications, 32(4), pp. 1073–1083. doi: 10.1016/j.eswa.2006.02.017.
Zachary, W. (1977) ‘An information flow model for conflict and fission in small groups’.
Zhang, X. et al. (2013) ‘Identifying influential nodes in complex networks with community structure’, Knowledge-Based Systems. Elsevier B.V., 42(4), pp. 74–84. doi: 10.1016/j.knosys.2013.01.017.
Zhao, J. et al. (2015) ‘Identifying influential nodes based on graph signal processing in complex networks’, Chinese Physics B, 24(5). doi: 10.1088/1674-1056/24/5/058904.
Zhao, X. et al. (2017) ‘Evaluating Influential Nodes in Social Networks by Local Centrality with a Coefficient’, ISPRS International Journal of Geo-Information, 6(2), p. 35. doi: 10.3390/ijgi6020035.
Zhao, Y., Li, S. and Jin, F. (2016) ‘Identification of influential nodes in social networks with community structure based on label propagation’, Neurocomputing. Elsevier, 210, pp. 34–44. doi: 10.1016/j.neucom.2015.11.125.
Zhou, C. et al. (2014) ‘An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in Social Networks’. doi: 10.1145/2567948.2577336.
Zhou, J., Zhang, Y. and Cheng, J. (2014) ‘Preference-based mining of top-K influential nodes in social networks’, Future Generation Computer Systems. North-Holland, 31, pp. 40–47. doi: 10.1016/J.FUTURE.2012.06.011.
Zhu, J., Liu, Y. and Yin, X. (2017) ‘A New Structure-Hole-Based Algorithm For Influence Maximization in Large Online Social Networks’, IEEE Access, 5(c), pp. 23405–23412. doi: 10.1109/ACCESS.2017.2758353.
Journal of Industrial and Systems Engineering
Volume 13, Issue 3
July 2021
Pages 16-40

Files

History

  • Receive Date: 01 March 2021
  • Revise Date: 07 April 2021
  • Accept Date: 23 June 2021

Share

How to cite

Statistics