The Intervention of Community Evolution Based on Markov Decision Process

doi:10.12068/j.issn.1005-3026.2022.11.003

Abstract

Abstract: The evolution of the community always tends to be complex and changeable. It becomes an important issue in the field of social networks about how to conduct personalized intervention on communities which are embedded in the network and make different communities evolve toward to different aims. Based on the intervention framework of community evolution， an intervention model based on Markov decision process(MDP)was proposed with the perspective of state transition. With the score of the state dimension and intervention goal， this model establishes the corresponding relationship between the evolution process and MDP， and then models the state， action， and reward in evolution process. Meanwhile， the expected reward of community evolution corresponds to the researcher′s reward. By solving the MDP， the community evolution can be effectively intervened. The experiment results indicated that the community evolution intervention model based on MDP can intervene the community evolution on different true data sets.

Key words: community evolution; community intervention; Markov decision process(MDP)

CLC Number:

CHAI Pei-hua， MAN Jun-yi， ZENG Yi-feng， CAO Lang-cai. The Intervention of Community Evolution Based on Markov Decision Process[J]. Journal of Northeastern University(Natural Science), 2022, 43(11): 1536-1543.

References

[1]Liu L Y，Xu L L，Wang Z，et al.Community detection based on structure and content:a content propagation perspective［C］// 2015 IEEE International Conference on Data Mining.Atlantic City，2015:271-280.
[2]Malek J，Hocine C，Chantal C，et al.Community detection algorithm evaluation with ground-truth data ［J］.Physica A:Statistical Mechanics and Its Applications，2018，492:651-706.
[3]吴斌.虚拟社区发现及演化分析研究［J］.科技纵览，2017(12):70-71.(Wu Bin.Discovery and evolution analysis of virtual communities［J］.IEEE Spectrum，2017(12):70-71.)
[4]Wang Z，Li Z，Yuan G，et al.Tracking the evolution of overlapping communities in dynamic social networks［J］.Knowledge-Based Systems，2018，157:81-97.
[5]Castellano C，Fortunato S，Loreto V.Statistical physics of social dynamics ［J］.Reviews of Modern Physics， 2009，81(2):591-646.
[6]Radicchi F，Castellano C，Cecconi F，et al. Defining and identifying communities in networks ［J］.Proceedings of The National Academy of Sciences，2004，101(9):2658-2663.
[7]Yang B，Liu D Y.Force-based incremental algorithm for mining community structure in dynamic network ［J］.Journal of Computer Science and Technology，2006，21(3):393-400.
[8]陈福集，杜锦锦.网络舆情监测技术研究及应用综述［J］.情报探索，2014(5):16-18.(Chen Fu-ji，Du Jin-jin.Review of studies and application of internet public opinion monitoring technologies ［J］.Information Research，2014(5):16-18.)
[9]Bródka P，Saganowski S，Kazienko P.GED:the method for group evolution discovery in social networks ［J］.Social Network Analysis and Mining，2013，3(1):1-14.
[10]Sutton R，Barto A.Reinforcement learning:an introduction［M］.Cambridge:MIT Press，2018.
[11]Palla G，Derenyi I，Farkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society ［J］.Nature，2005，435(7043):814-818.
[12]Man J Y，Zhu J R，Cao L C.Multi-step community evolution prediction methods via Markov chain and classifier chain ［C］// Proceedings of 2019 Chinese Control Conference.Guangzhou，2019:7950-7955.
[13]Kaufman L，Rousseeuw P J.Finding groups in data:an introduction to cluster analysis ［M］.New York:John Wiley & Sons，1990.
[14]Newman M E J.Networks:an introduction ［M］.New York:Oxford University Press，2012.
[15]Brodka P，Musial K，Kazienko N P.A performance of centrality calculation in social networks ［C］// Proceedings of the 2009 International Conference on Computational Aspects of Social Network.Fontainebleau，2009:24-31.
[16]Ley M.DBLP-some lessons learned ［J］.Proceedings of Very Large Data Base Endowment，2009，2(2):1493-1500.