近年來，分群檢測是被廣泛研究題目之一，過去已經有許多文獻提出不同的分群檢測演算法，然而隨著社群網路成長快速，相較於計算整個網路的全域性分群演算法，區域性分群演算法顯得更有效率，大多數現有的區域性分群演算法使用貪婪算法選擇起始點，並使用優化函數將其擴展為社區，但是使用此種作法，無法確保最終社區包含目標節點。在本文研究
中，我們提出了一種通過檢測和擴展局部結構來探索目標節點的區域性社區的方法，從而增加了目標節點能夠識別其相應社區的可能性，我們提出的演算法主要使用鄰域聚類來選擇起始點，然後才開始進行社區擴展的方法，其中分為兩個階段擴展過程，我們首先找到起始點的鄰域集群，然後根據區域性模塊化來擴展社區。在實驗中，當使用各種起始點選擇策略應
用於合成網絡和真實網絡時，我們的演算法都是優於最先進的演算法。

Local community detection is far more efficient than global community detection. Most existing local community detection algorithms select a seed node using a greedy algorithm and expand it into a community using optimization functions. However, using this approach, there is no way to ensure that the final community contains the target node. In this paper, we propose
a method for exploring local communities of the target node (ELCTN) through the detection and expansion of local structure, thereby increasing the likelihood that the target node will be able to identify its corresponding community. The proposed scheme uses neighborhood clustering for the selection of the initial seed node. Community extension is a two-stage expansion process in which we first find the neighborhood cluster of the seed node, and then expand the community based on local modularity. In experiments, ELCTN outperformed state-of the-art algorithms when applied to synthetic as well as real-world networks using a variety of seed-selection strategies.

[1] Y. Zhu, E. Zhong, S. J. Pan, X. Wang, M. Zhou, and Q. Yang, “Predicting user activity
level in social networks.” in CIKM, Q. He, A. Iyengar, W. Nejdl, J. Pei, and R. Rastogi,
Eds. ACM, 2013, pp. 159–168.
[2] G. Zhao, M.-L. Lee, W. Hsu, W. Chen, and H. Hu, “Community-based user recommendation
in uni-directional social networks.” in CIKM, Q. He, A. Iyengar, W. Nejdl, J. Pei,
and R. Rastogi, Eds. ACM, 2013, pp. 189–198.
[3] X. Wang and G. Sukthankar, “Multi-label relational neighbor classification using social
context features.” in KDD, ser. KDD ’13, I. S. Dhillon, Y. Koren, R. Ghani, T. E. Senator,
P. Bradley, R. Parekh, J. He, R. L. Grossman, and R. Uthurusamy, Eds. New York, NY,
USA: ACM, 2013, pp. 464–472.
[4] H. Li, X. Ma, F. Wang, J. Liu, and K. Xu, “On popularity prediction of videos shared in
online social networks.” in CIKM, Q. He, A. Iyengar, W. Nejdl, J. Pei, and R. Rastogi,
Eds. ACM, 2013, pp. 169–178.
[5] X. Kong, J. Zhang, and P. S. Yu, “Inferring anchor links across multiple heterogeneous
social networks.” in CIKM, Q. He, A. Iyengar, W. Nejdl, J. Pei, and R. Rastogi, Eds.
ACM, 2013, pp. 179–188.
[6] C. C. Cao, Y. Tong, L. Chen, and H. V. Jagadish, “Wisemarket: a new paradigm for
managing wisdom of online social users.” in KDD, I. S. Dhillon, Y. Koren, R. Ghani, T. E.
Senator, P. Bradley, R. Parekh, J. He, R. L. Grossman, and R. Uthurusamy, Eds. ACM,
2013, pp. 455–463.
[7] F. Moradi, T. Olovsson, and P. Tsigas, “A local seed selection algorithm for overlapping
community detection.” in ASONAM, X. Wu, M. Ester, and G. Xu, Eds. IEEE Computer
Society, 2014, pp. 1–8.
[8] X. Ding, J. Zhang, and J. Yang, “A robust two-stage algorithm for local community
detection.” Knowl.-Based Syst., vol. 152, pp. 188–199, 2018.
[9] Y. Zhou, G. Sun, Y. Xing, R. Zhou, and Z. Wang, “Local community detection algorithm
based on minimal cluster.” Applied Comp. Int. Soft Computing, vol. 2016, pp. 3 217 612:1–
3 217 612:11, 2016.
[10] S. Scellato, A. Noulas, and C. Mascolo, “Exploiting place features in link prediction on
location-based social networks,” in KDD, C. Apt´e, J. Ghosh, and P. Smyth, Eds. ACM,
2011, pp. 1046–1054.
[11] J. Zhang, X. Kong, and P. S. Yu, “Transferring heterogeneous links across location-based
social networks.” in WSDM, B. Carterette, F. Diaz, C. Castillo, and D. Metzler, Eds.
ACM, 2014, pp. 303–312.
[12] H. Bagci and P. Karagoz, “Context-aware friend recommendation for location based social
networks using random walk.” in WWW (Companion Volume), J. Bourdeau, J. Hendler,
R. Nkambou, I. Horrocks, and B. Y. Zhao, Eds. ACM, 2016, pp. 531–536.
[13] W. Feng and J. Wang, “Incorporating heterogeneous information for personalized tag
recommendation in social tagging systems,” in Proceedings of the 18th ACM SIGKDD
international conference on Knowledge discovery and data mining, ser. KDD ’12. New
York, NY, USA: ACM, 2012, pp. 1276–1284.
[14] X. Yang, H. Steck, and Y. Liu, “Circle-based recommendation in online social networks.”
in KDD, Q. Yang, D. Agarwal, and J. Pei, Eds. ACM, 2012, pp. 1267–1275.
[15] H. Yin, Y. Sun, B. Cui, Z. Hu, and L. Chen, “Lcars: a location-content-aware recommender
system.” in KDD, I. S. Dhillon, Y. Koren, R. Ghani, T. E. Senator, P. Bradley, R. Parekh,
J. He, R. L. Grossman, and R. Uthurusamy, Eds. ACM, 2013, pp. 221–229.
[16] Y. Tang, X. Xiao, and Y. Shi, “Influence maximization: Near-optimal time complexity
meets practical efficiency.” CoRR, 2014.
[17] Y. Tang, Y. Shi, and X. Xiao, “Influence maximization in near-linear time: A martingale
approach.” in SIGMOD Conference, T. K. Sellis, S. B. Davidson, and Z. G. Ives, Eds.
ACM, 2015, pp. 1539–1554.
[18] H. T. Nguyen, M. T. Thai, and T. N. Dinh, “Stop-and-stare: Optimal sampling algorithms
for viral marketing in billion-scale networks.” in SIGMOD Conference, F. ¨ Ozcan,
G. Koutrika, and S. Madden, Eds. ACM, 2016, pp. 695–710.
[19] A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi, “Power in
unity: forming teams in large-scale community systems.” in CIKM, J. Huang, N. Koudas,
G. J. F. Jones, X. Wu, K. Collins-Thompson, and A. An, Eds. ACM, 2010, pp. 599–608.
[20] G. Kasneci, M. Ramanath, M. Sozio, F. M. Suchanek, and G. Weikum, “Star: Steiner-tree
approximation in relationship graphs.” in ICDE, Y. E. Ioannidis, D. L. Lee, and R. T. Ng,
Eds. IEEE Computer Society, 2009, pp. 868–879.
[21] Q. Liu, T. Luo, R. Tang, and S. Bressan, “An efficient and truthful pricing mechanism for
team formation in crowdsourcing markets.” CoRR, vol. abs/1812.04865, 2018.
[22] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks.”
2004.
[23] A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large
networks,” Physical Review E, vol. 70, p. 066111, 2004.
[24] S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, pp. 75–174,
2010.
[25] M. Newman, “Detecting community structure in networks,” The European Physical Journal
B-Condensed Matter, vol. 38, no. 2, pp. 321–330, 2004.
[26] M. E. Newman, “Fast algorithm for detecting community structure in networks,” Physical
review E, vol. 69, no. 6, p. 066133, 2004.
[27] H. Shen and X. Cheng, “Spectral methods for the detection of network community structure:
a comparative analysis,” CoRR, vol. abs/1010.4098, 2010.
[28] V. Blondel, J. Guillaume, R. Lambiotte, and E. Mech, J. Stat. Mech, p. P10008, 2008.
[29] S. Li, H. Lou, W. Jiang, and J. Tang, “Detecting community structure via synchronous
label propagation.” Neurocomputing, vol. 151, pp. 1063–1075, 2015.
[30] J. P. Bagrow, “Evaluating local community methods in networks,” Journal of Statistical
Mechanics: Theory and Experiment, vol. 2008, no. 05, p. P05001, may 2008. [Online].
Available: https://doi.org/10.1088%2F1742-5468%2F2008%2F05%2Fp05001
[31] Y.Wu, H. Huang, Z. Hao, and F. Chen, “Local community detection using link similarity.”
J. Comput. Sci. Technol., vol. 27, no. 6, pp. 1261–1268, 2012.
[32] J. P. Bagrow and E. M. Bollt, “Local method for detecting communities,” Phys. Rev.
E, vol. 72, p. 046108, Oct 2005. [Online]. Available: https://link.aps.org/doi/10.1103/
PhysRevE.72.046108
[33] A. Clauset, “Finding local community structure in networks,” Phys. Rev. E, vol. 72, p.
026132, Aug. 2005.
[34] F. Luo, J. Wang, and E. Promislow, “Exploring local community structures in large networks,”
Web Intelligence and Agent Systems, vol. 6, no. 4, pp. 387–400, 2008.
[35] C. Shang, S. Feng, Z. Zhao, and J. Fan, “Efficiently detecting overlapping communities
using seeding and semi-supervised learning.” Int. J. Machine Learning Cybernetics, vol. 8,
no. 2, pp. 455–468, 2017.
[36] X. Bai, P. Yang, and X. Shi, “An overlapping community detection algorithm based on
density peaks.” Neurocomputing, vol. 226, pp. 7–15, 2017.
[37] M. F. Qiong Chen, Ting-Ting Wu, “Detecting local community structures in complex
networks based on local degree central nodes,” Physica A: Statistical Mechanics and its
Applications, vol. 392, pp. 529–537, 2013.
[38] D. F. Gleich and C. Seshadhri, “Vertex neighborhoods, low conductance cuts, and good
seeds for local community methods.” in KDD, Q. Yang, D. Agarwal, and J. Pei, Eds.
ACM, 2012, pp. 597–605.
[39] Lv Lin Tao, Shen Bing, Yang Yu Xiang, and Tan Fang, “A local complex network communities’
discovery algorithm,” in 2013 IEEE 4th International Conference on Software
Engineering and Service Science, May 2013, pp. 787–790.
[40] A. Lancichinetti and S. Fortunato, “Benchmarks for testing community detection algorithms
on directed and weighted graphs with overlapping communities,” Phys. Rev. E,
vol. 80, no. 1, p. 016118, Jul. 2009.
[41] W. Zachary, “An information flow model for conflict and fission in small groups,” Journal
of Anthropological Research, vol. 33, pp. 452–473, 1977.
[42] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,”
PNAS, vol. 99, no. 12, pp. 7821–7826, June 2002.
[43] J. Yang and J. Leskovec, “Defining and evaluating network communities based on groundtruth,”
Knowledge and Information Systems, vol. 42, no. 1, pp. 181–213, 2015.
[44] L. Danon, A. D´ıaz-Guilera, J. Duch, and A. Arenas, “Comparing community structure
identification,” J. Stat. Mech., vol. 9, p. 8, 2005.
[45] W. P. Li Jianhua, Wang Xiaofeng, “Review on community detection methods based on
local optimization,” Bulletin of Chinese Academy of Sciences, pp. 238–247, 2015.