Community Structure-based Re-ranking Information Influence Maximization Algorithm for Typhoon Disasters

Zufeng Zhong, Hongyan Yang

Ekoloji, 2019, Issue 107, Pages: 453-462, Article No: e107054

OPEN ACCESS

Download Full Text (PDF)

Abstract

This paper proposes a new community structure-based influence maximization algorithm (CSRR) based on the topological structure of diffusion networks for typhoon disasters. We developed the proposed algorithm by using pre-existing community detection algorithms to detect the community structures hidden in the networks and identify the TOP-M nodes which span a relatively large number of communities; We found the TOP-K nodes at large distances and used them as the initial diffusers of influence through re-ranking of the M nodes. A typhoon disaster event in the Leizhou Peninsula, China, is used as an example to validate the effectiveness and feasibility of the proposed Algorithm. Our test results show that this algorithm provides higher diffusion speed and larger diffusion range than traditional-influence maximization algorithms in the typhoon disaster.

Keywords

typhoon disasters, online social network, influence, community structure, re-ranking, China

References

  • Acar A, Muraki Y (2011) Twitter for crisis communication: lessons learned from Japan’s tsunami disaster. International Journal of Web Based Communities, 7(3): 392-402.
  • Aggarwal CC, Khan A, Yan X (2011) On Flow Authority Discovery in Social Networks. SDM: 522-533.
  • Ahn Y Y, Bagrow JP, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature, 466(7307): 761-764.
  • Blondel VD, Guillaume JL, Lambiotte R, et al. (2008) Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, (10): P10008.
  • Bozorgi A, Haghighi H, Zahedi MS, et al. (2016) INCIM: A community-based algorithm for influence maximization problem under the linear threshold model. Information Processing & Management, 52(6): 1188-1199.
  • Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM: 199-208.
  • China, & Marine Bureau (2015) China marine disaster Bulletin.
  • China, & Marine Bureau (2016) China marine disaster Bulletin.
  • Clauset A, Newman MEJ, Moore C (2004) Finding community structure in very large networks. Physical review E, 70(6): 066111.
  • Dang TA, Viennet E (2012) Community detection based on structural and attribute similarities. International Conference on Digital Society (ICDS): 7-12.
  • Deitrick W, Hu W (2013) Mutually enhancing community detection and sentiment analysis on twitter networks.
  • Goldenberg J, Libai B, Muller E (2001) Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing letters, 12(3): 211-223.
  • Granovetter M (1978) Threshold models of collective behavior. American journal of sociology: 1420-1443.
  • Gregory S (2010) Finding overlapping communities in networks by label propagation. New Journal of Physics, 12(10): 103018.
  • Hansen LK, Arvidsson A, Nielsen FÅ, et al. (2011) Good friends, bad news-affect and virality in twitter. Future information technology. Springer Berlin Heidelberg: 34-43.
  • Jiang Q, Song G, Cong G, et al. (2011) Simulated Annealing Based Influence Maximization in Social Networks. AAAI, 11: 127-132.
  • Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM: 137-146.
  • Kewalramani MN (2011) Community detection in Twitter. University of Maryland, Baltimore County.
  • Kimura M, Saito K (2006) Tractable models for information diffusion in social networks. European Conference on Principles of Data Mining and Knowledge Discovery. Springer Berlin Heidelberg: 259-271.
  • Li L (2010) Research on influence models and algorithms of social networks. Beijing Jiaotong University.
  • Lu Z, Zhang W, Wu W, et al. (2012) The complexity of influence maximization problem in the deterministic linear threshold model. Journal of combinatorial optimization, 24(3): 374-378.
  • Mashayekhi Y, Meybodi MR, Rezvanian A (2018) Weighted estimation of information diffusion probabilities for independent cascade model. 2018 4th International Conference on Web Research (ICWR). IEEE: 63-69.
  • Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Physical review E, 69(2): 026113.
  • O’Connor B, Balasubramanyan R, Routledge BR, et al. (2010) From tweets to polls: Linking text sentiment to public opinion time series. ICWSM, 11(122-129): 1-2.
  • Ou J, Duan Z, Chang L (2002) Typhoon risk analysis for key coastal cities in southeast China. Journal of Natural Disasters, 11(4): 9-17.
  • Palla G, Derényi I, Farkas I, et al. (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043): 814-818.
  • Peng H, Zhao D, Li L, et al. (2016) An improved label propagation algorithm using average node energy in complex networks. Physica A: Statistical Mechanics and its Applications, 460: 98-104.
  • Plotnick L, Turoff M, White C (2011) Partially Distributed Emergency Teams: Considerations of Decision Support for Virtual Communities of Practice. Supporting Real Time Decision-Making. Springer US: 203-220.
  • Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3): 036106.
  • Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM: 61-70.
  • Schmidt S, Kemfert C, Höppe P (2010) The impact of socio-economics and climate change on tropical cyclone losses in the USA. Regional Environmental Change, 10(1): 13-26.
  • Starbird K, Palen L (2010) Pass it on? Retweeting in mass emergency. International Community on Information Systems for Crisis Response and Management.
  • Steinhaeuser K, Chawla NV (2010) Identifying and evaluating community structure in complex networks. Pattern Recognition Letters, 31(5): 413-421.
  • Sun H, Liu J, Huang J, et al. (2015) CenLP: A centrality-based label propagation algorithm for community detection in networks. Physica A: Statistical Mechanics and its Applications, 436: 767-780.
  • Sun J, Tang J (2011) A survey of models and algorithms for social influence analysis. Social Network Data Analytics. Springer US: 177-214.
  • Wakita K, Tsurumi T (2007) Finding community structure in mega-scale social networks: [extended abstract] Proceedings of the 16th international conference on World Wide Web. ACM: 1275-1276.
  • Xie J, Chen M, Szymanski BK (2013) LabelrankT: Incremental community detection in dynamic networks via label propagation. Proceedings of the Workshop on Dynamic Networks Management and Mining. ACM: 25-32.
  • Xie J, Szymanski BK (2012) Towards linear time overlapping community detection in social networks. Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer Berlin Heidelberg: 25-36.
  • Xie J, Szymanski BK (2013) Labelrank: A stabilized label propagation algorithm for community detection in networks. Network Science Workshop (NSW), 2013 IEEE 2nd. IEEE: 138-143.
  • Xie J, Szymanski BK, Liu X (2011) Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. 2011 IEEE 11th International Conference on Data Mining Workshops. IEEE: 344-349.