随着现代信息技术的广泛应用，社会学、统计物理学、经济管理学、生物学、计算机科学等领域的复杂网络数量急速增长，网络规模日渐庞大，分析一个网络的全局结构特征逐渐变得困难。在一些应用场景中，人们只关心特定节点所属的社区，因此局部社区发现受到众多研究者的关注。与全局社区发现相比，它更关注局部的网络结构，能够返回更加个性化的社区。本文针对当前局部社区发现算法存在的问题进行了如下研究：

      1.针对静态网络，本文提出一种基于Monte-Carlo迭代求解策略的局部社区发现算法。现有局部社区发现算法采用基于贪心策略的逐步扩张方式来发现目标社区，容易过早收敛，难以获得目标社区的全部节点。本文所提算法在社区扩张阶段，根据节点对目标函数的贡献比例为所有邻接候选节点赋予选择概率，并据此概率随机选择节点；为避免随机选择导致扩张方向偏离目标社区，根据社区质量下降程度判断是否触发节点淘汰机制；在节点淘汰机制中，根据节点相似度为已加入的节点赋予淘汰概率，并据此概率随机删除节点。重复以上步骤，直至达到迭代终止条件。实验结果表明，所提算法的性能相较传统算法有大幅度提升。

       2.针对动态网络，将上述算法扩展为增量式的动态局部社区发现算法。现有局部社区发现算法往往将动态网络按照时间片形式进行划分，然后对每个时间片的网络快照均执行静态网络局部社区发现算法，会造成大量的冗余计算，效率非常低下。本文首先使用基于Monte-Carlo迭代求解策略的局部社区发现算法获得初始的局部社区，然后从第二个时间片开始，在前一时间片网络的局部社区的基础上，根据内聚度和外联度的变化情况对该局部社区进行相应的增量式操作。实验结果表明，在保证所发现局部社区质量的前提下，增量式算法在时间开销方面相较静态算法显著降低。

       3.结合上述研究内容，设计并实现了一个局部社区发现系统。该系统集成了多种局部社区发现算法，可对所选数据集中的待查寻节点进行局部社区发现操作，并将算法的执行结果进行直观展示。

      With the wide application lor='red'>of modern information technology, the number lor='red'>of complex networks in sociology, statistical physics, economic management, biology, computer science and other fields has grown rapidly, and the scale lor='red'>of the network has become larger and larger. Analyzing the global structural characteristics lor='red'>of a network has gradually become difficulty. In some application scenarios, people only care about the community to which a particular node belongs, so local community detection has attracted the attention lor='red'>of many researchers. Compared with global community detection, it pays more attention to the local network structure and can return more personalized communities. In this paper, the problems existing in the current local community detection algorithm are studied as follows:

      1.For static networks, this paper proposes a local community detection algorithm based on Monte-Carlo iterative solution strategy. The existing local community detection algorithm uses a gradual expansion method based on a greedy strategy to detect the target community, which is prone to premature convergence and difficult to obtain all nodes lor='red'>of the target community. In the community expansion stage, the algorithm proposed in this paper assigns selection probability to all adjacent candidate nodes according to the contribution ratio lor='red'>of nodes to the objective function, and randomly selects nodes according to this probability. In order to avoid random selection leading to the expansion direction deviating from the target community, the node elimination mechanism should be triggered according to the community quality decline degree. In the node elimination mechanism, the nodes that have joined are assigned elimination probability according to node similarity, and the nodes are deleted randomly according to the probability. Repeat the above steps until the iteration termination condition is reached. Experimental results show that the performance lor='red'>of the proposed algorithm is greatly improved compared with traditional algorithms.

      2.For dynamic networks, the algorithm is extended to an incremental dynamic local community detection algorithm. Existing local community detection algorithms usually divide dynamic networks into time slices, and then implement static network local community detection algorithm for network snapshots lor='red'>of each time slice, which will cause a lot lor='red'>of redundant calculation and very low efficiency. In this paper, the local community detection algorithm based on Monte-Carlo iterative solution strategy is firstly used to obtain the initial local community. Then, from the second time slice, based on the local community lor='red'>of the previous time slice network, the corresponding incremental operation is carried out on the local community according to the changes lor='red'>of cohesion and connectedness. The experimental results show that the incremental algorithm can significantly reduce the time cost compared with the static algorithm on the premise lor='red'>of ensuring the quality lor='red'>of the detected local communities.

      3.Combined with the above research content, a local community detection system is designed and implemented. The system integrates a variety lor='red'>of local community detection algorithms, which can perform local community detection operations on the nodes to be searched in the selected dataset, and visually display the execution results lor='red'>of the algorithms.

[1] 周强. 复杂网络社区发现算法研究[D]. 电子科技大学, 2020.

[2] Fang Y , Huang X , Qin L , et al. A survey of community search over big graphs[J]. The VLDB Journal, 2020, 29(1):353-392.

[3] Strogatz S H. Exploring complex networks[J]. Nature, 2001, 410(6825): 268-276.

[4] Fang Y , Huang X , Qin L , et al. A survey of community search over big graphs[J]. The VLDB Journal, 2020, 29(1):353-392.

[5] Zarayeneh N, Kalyanaraman A. A fast and efficient incremental approach toward dynamic community detection[C]//Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2019: 9-16.

[6] Jian X, Wang Y, Chen L. Effective and efficient relational community detection and search in large dynamic heterogeneous information networks[J]. Proceedings of the VLDB Endowment, 2020, 13(10): 1723-1736.

[7] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[8] 邓琨, 李文平, 陈丽, 刘星妍. 一种新的基于标签传播的复杂网络重叠社区识别算法[J]. 控制与决策, 2020, 35(11): 2733-2742.

[9] He K, Shi P, Bindel D, et al. Krylov subspace approximation for local community detection in large networks[J]. ACM Transactions on Knowledge Detection from Data (TKDD), 2019, 13(5): 1-30.

[10] Li M, Liu R R, Lü L, et al. Percolation on complex networks: Theory and application[J]. Physics Reports, 2021, 907: 1-68.

[11] Huang X, Chen D, Ren T, et al. A survey of community detection methods in multilayer networks[J]. Data Mining and Knowledge Detection, 2021, 35(1): 1-45.

[12] J Jin D, Yu Z, Jiao P, et al. A survey of community detection approaches: From statistical modeling to deep learning. arXiv 2021[J]. arXiv preprint arXiv:2101.01669.

[13] Verma P, Goyal R. Influence propagation based community detection in complex networks[J]. Machine Learning with Applications, 2021, 3: 100019.

[14] Gawande N, Ghosh S, Halappanavar M, et al. Towards scaling community detection on distributed-memory heterogeneous systems[J]. Parallel Computing, 2022, 111: 102898.

[15] Sozio M, Gionis A. The community-search problem and how to plan a successful cocktail party[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Detection and Data Mining. 2010: 939-948.

[16] Dilmaghani S, Brust M R, Ribeiro C H C, et al. From communities to protein complexes: A local community detection algorithm on PPI networks[J]. PloS One, 2022, 17(1): e0260484.

[17] Liu S, Xia Z. A two-stage BFS local community detection algorithm based on node transfer similarity and Local Clustering Coefficient[J]. Physica A: Statistical Mechanics and its Applications, 2020, 537: 122717.

[18] Yin Y, Zhao Y, Li H, et al. Multi-objective evolutionary clustering for large-scale dynamic community detection[J]. Information Sciences, 2021, 549: 269-287.

[19] Mohammadi M, Fazlali M, Hosseinzadeh M. Parallel Louvain Community Detection Algorithm Based on Dynamic Thread Assignment on Graphic Processing Unit[J]. Journal of Electrical and Computer Engineering Innovations (JECEI), 2022, 10(1): 75-88.

[20] Islam N U, Sunitha R. A Comprehensive Review on Deep Learning-Based Community Detection in Networks[J]. Emerging Research in Computing, Information, Communication and Applications, 2022: 567-579.

[21] Chaudhary N, Thakur H K, Dwivedi R. An ensemble model to optimize modularity in dynamic bipartite networks[J]. International Journal of System Assurance Engineering and Management, 2022: 1-13.

[22] Clauset A. Finding local community structure in networks[J]. Physical Review E, 2005, 72(2): 026132.

[23] Luo F, Wang J Z, Promislow E. Exploring local community structures in large networks[J]. Web Intelligence and Agent Systems: An International Journal, 2008, 6(4): 387-400.

[24] Luo W, Zhang D, Jiang H, et al. Local community detection with the dynamic membership function[J]. IEEE Transactions on Fuzzy Systems, 2018, 26(5): 3136-3150.

[25] 张道福. 局部社区发现算法研究[D]. 中国科学技术大学, 2018.

[26] Cui W, Xiao Y, Wang H, et al. Local search of communities in large graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014: 991-1002.

[27] Li C, Zhang F, Zhang Y, et al. Efficient progressive minimum k-core search[J]. Proceedings of the VLDB Endowment, 2019, 13(3): 362-375.

[28] Fang Y, Wang Z, Cheng R, et al. Effective and efficient community search over large directed graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(11): 2093-2107.

[29] Huang X, Cheng H, Qin L, et al. Querying k-truss community in large and dynamic graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014: 1311-1322.

[30] Akbas E, Zhao P. Truss-based community search: a truss-equivalence based indexing approach[J]. Proceedings of the VLDB Endowment, 2017, 10(11): 1298-1309.

[31] Xie X, Zhang J, Wang W, et al. Attributed community search considering community focusing and latent relationship[J]. Knowledge and Information Systems, 2022, 64(3): 799-829.

[32] Yuan L, Qin L, Zhang W, et al. Index-based densest clique percolation community search in networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 30(5): 922-935.

[33] Wu J, Li C M, Jiang L, et al. Local search for diversified top-k clique search problem[J]. Computers & Operations Research, 2020, 116: 104867.

[34] Tang Z, Tang Y, Li C, et al. A fast local community detection algorithm in complex networks[J]. World Wide Web, 2021, 24(6): 1929-1955.

[35] Wu Y, Jin R, Li J, et al. Robust local community detection: on free rider effect and its elimination[J]. Proceedings of the VLDB Endowment, 2015, 8(7): 798-809.

[36] Bian Y, Ni J, Cheng W, et al. Many heads are better than one: Local community detection by the multi-walker chain[C]//2017 IEEE International Conference on Data Mining (ICDM). IEEE, 2017: 21-30.

[37] 吴卫江,桑睿彤,郑艺峰. 基于限制性随机游走局部谱近似社区发现算法[J]. 计算机工程与设计,2021,42(9):2472-2477.

[38] Luo W, Lu N, Ni L, et al. Local community detection by the nearest nodes with greater centrality[J]. Information Sciences, 2020, 517: 377-392.

[39] 刘井莲, 王大玲, 冯时, 等. 一种基于模糊相似关系的局部社区发现方法[J]. Journal of Software, 2020, 31(11): 3481-3491.

[40] 赵卫绩, 张凤斌, 刘井莲. 一种基于加权共同邻居相似度的局部社区发现算法[J]. 南京大学学报: 自然科学版, 2018 (4): 751-757.

[41] Liu J, Shao Y, Su S. Multiple Local Community Detection via High-Quality Seed Identification over Both Static and Dynamic Networks[J]. Data Science and Engineering, 2021: 1-16.

[42] Aghaalizadeh S, Afshord S T, Bouyer A, et al. A three-stage algorithm for local community detection based on the high node importance ranking in social networks[J]. Physica A: Statistical Mechanics and its Applications, 2021, 563: 125420.

[43] Huang J, Sun H, Liu Y, et al. Towards online multiresolution community detection in large-scale networks[J]. PloS One, 2011, 6(8): e23829.

[44] Ding X, Zhang J, Yang J. Node-community membership diversifies community structures: An overlapping community detection algorithm based on local expansion and boundary re-checking[J]. Knowledge-Based Systems, 2020, 198: 105935.

[45] Shang R, Zhang W, Zhang J, et al. Local community detection based on higher-order structure and edge information[J]. Physica A: Statistical Mechanics and its Applications, 2022, 587: 126513.

[46] 端祥宇, 袁冠, 孟凡荣. 动态社区发现方法研究综述[J]. 计算机科学与探索, 2021, 15(4): 612-630.

[47] 郭昆, 彭胜波, 陈羽中, 郭文忠. 基于密度聚类的增量动态社区发现算法[J]. 模式识别与人工智能, 2018, 31(11): 965-978.

[48] 朱腾云. 基于密度的增量动态社区发现算法研究[D]. 福州大学, 2019.

[49] Li C, Chen H, Li T, et al. A stable community detection approach for complex network based on density peak clustering and label propagation[J]. Applied Intelligence, 2022, 52(2): 1188-1208.

[50] Xie J, Szymanski B K. Labelrank: A stabilized label propagation algorithm for community detection in networks[C]//2013 IEEE 2nd Network Science Workshop (NSW). IEEE, 2013: 138-143.

[51] Sattari M, Zamanifar K. A cascade information diffusion based label propagation algorithm for community detection in dynamic social networks[J]. Journal of Computational Science, 2018, 25: 122-133.

[52] Zhang H, Dong B, Wu H, et al. A Multi-label Propagation Community Detection Algorithm for Dynamic Complex Networks[C]//International Conference on Advanced Information Systems Engineering. Springer, Cham, 2021: 467-482.

[53] Wang W, Jiao P, He D, et al. Autonomous overlapping community detection in temporal networks: A dynamic Bayesian nonnegative matrix factorization approach[J]. Knowledge-Based Systems, 2016, 110: 121-134.

[54] Niu X, Si W, Wu C Q. A label-based evolutionary computing approach to dynamic community detection[J]. Computer Communications, 2017, 108: 110-122.

[55] 李浩,杨海潇,张兰,黄欣,王海宁,康雁.改进离散蜉蝣算法的多目标动态网络社区发现[J/OL].计算机科学与探索:1-14[2022-06-01].http://kns.cnki.net/kcms/detail/11.5602.TP.20211014.2053.008.html.

[56] Li W, Zhou X, Yang C, et al. Multi-objective optimization algorithm based on characteristics fusion of dynamic social networks for community discovery[J]. Information Fusion, 2022, 79: 110-123.

[57] Guare J, Sandrich J, Loewenberg S A. Six degrees of separation[M]. LA Theatre Works, 2000.

[58] Albert R, Jeong H, Barabási A L. Diameter of the world-wide web[J]. Nature, 1999, 401(6749): 130-131.

[59] Barabási A L. Scale-free networks: a decade and beyond[J]. Science, 2009, 325(5939): 412-413.

[60] 顾炎. 社会网络中动态社区发现方法研究[D].南京邮电大学, 2017.

[61] Eggemann N, Noble S D. The clustering coefficient of a scale-free random graph[J]. Discrete Applied Mathematics, 2011, 159(10): 953-965.

[62] 聂世民. 社交网络中局部社区发现算法研究[D]. 中国人民公安大学, 2020.

[63] 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.

[64] Weinan E, Han J, Jentzen A. Algorithms for solving high dimensional pdes: From nonlinear monte carlo to machine learning[J]. Nonlinearity, 2021, 35(1): 278.

[65] Arnold U, Yildiz Ö. Economic risk analysis of decentralized renewable energy infrastructures–A Monte Carlo Simulation approach[J]. Renewable Energy, 2015, 77: 227-239.