社群網路結構檢測是近年來廣泛被研究的題目，過去已經有許多文獻提出分群檢測演算法，然而近年來社群網路資料成長快速，相較於需計算整個網路的全域性分群演算法，區域性分群演算法大多採取選擇社群核心及核心擴張的策略，僅需考慮社群網路上部分的資訊，更適合應用在大型的社群網路上。本研究提出了一個新穎的起始點選擇公式，藉由起始點選擇公式，可以選出一個位於社群中央的節點當作起始點。另外，現有的區域性社群演算法大多只探討核心周圍的節點是否可加入核心社群中，但只考慮單一節點會失去太多的資訊，造成社群檢測效果不佳，因此本研究將針對過去區域性分群演算法的缺點，提出一套區域性擴展之社群檢測演算法，選擇社群核心及考慮核心周圍節點所形成的鄰居社群，藉由此方法能夠解決中繼點分群之問題。本研究更進一步使用標籤傳遞方法使得我們可以一次性的篩選鄰居社群是否可以被加入社群核心中，不僅降低了執行時間，進而達到更準確的社群檢測。實驗我們使用LFR Benchmark產生不同連結緊密度以及不同點數的複雜網路圖以及現實世界的網路圖，並與過去的演算法做比較，另外我們將本研究所提出的起始點選擇方法與現存的起始點選擇方法做比較，我們所提出的演算以及起始點選擇方法皆能夠在幾乎所有的網路圖上有較高的分群準確度。而且我們的方法對於點數來說更達到線性的時間複雜度。我們更進一步與全域性社群檢測方法做比較，我們的方法甚至與全域性社群檢測方法有極為相近的準確度。

There have been more and more researches on community discovery in complex networks. Expanding of a source node into a community is one of the most successful methods for local community detection, especially when the global structure of the network is not accessible. In this paper, we propose CLOSE algorithm, Local Community Detection by LOcal Structure Expansion, based on the local expansion technique in the community detection. In CLOSE, we propose a novel connective function to identify a better source node. The node is in the center of a highly connected component of a graph. CLOSE selects a group of nodes instead of a single node to be the seed for the expansion of a local community. In addition, using the neighboring group can identify a suitable community for a hub node. Moreover, the expansion strategy is based on the label propagation technique instead of local community measurements. In experiments, we compare the performance of CLOSE with previous methods both on synthetic networks from the LFR Benchmark and real-world networks. We also examine the merit of the source node selection strategy. Both source node selection and community detection in CLOSE outperform previous algorithms. It is worth to mansion that the time complexity of CLOSE is linear to the number of nodes.

[1] E. Alm and A. P. Arkin. Biological networks. In Current Opinion in Structural Biology,
pages 193–202, 2003.
[2] J. P. Bagrow. Evaluating local community structure in networks. Journal of Statistical
Mechanics Theory and Experiment, 2008(P05001), 2008.
[3] J. P. Bagrow and E. Bollt. Local method for detecting communities. Physical Review E,
72(046108), 2005.
[4] A.-L. Barabasi and Z. N. Oltvai. Network biology: Understanding the cell’s functional
organization. In Nature Reviews Genetics 5, pages 101–113, 2004.
[5] B. Bollobas and O. Riordan. Clique percolation. Random Structures & Algorithms,
35(3):294–322, 2009.
[6] R. Bourqui, F. Gilbert, P. Simonetto, F. Zaidi, U. Sharan, and F. Jourdan. Detecting
structural changes and command hierarchies in dynamic social networks. In Social Network
Analysis and Mining, International Conference on Advances, pages 83–88, 2009.
[7] D. Chen, Y. Fu, and M. Shang. An efficient algorithm for community detection in complex
networks. In Workshop on Social Network Mining and Analysis (SNA-KDD), pages 244–
247, 2012.
[8] J. Chen, O. Za¨ıane, and R. Goebel. Local community identification in social networks.
In International Conference on Advances in Social Networks Analysis and Mining
(ASONAM), pages 237–242, 2009.
[9] A. Clauset. Finding local community structure in networks. Physical Review E, 72(026132),
2005.
[10] L. Danon, J. Duch, A. D´ıaz-Guilera, and A. Arenas. Comparing community structure
identification. Journal of Statistical Mechanics, pages 76–99, 2005.
[11] D. J. de S. Price. Networks of scientific papers. Science, 149(3683):510–515, 1965.
[12] S. Fortunato. Community detection in graphs. Physics Reports, 486:75–174, 2010.
[13] M. Girvan and M. E. J. Newman. Community structure in social and biological networks.
In Proceedings of National Academy of Sciences, pages 7821–7826, 2002.
[14] D. F. Gleich and C. Seshadhri. Vertex neighborhoods, low conductance cuts, and good
seeds for local community methods. In International Conference on Knowledge Discovery
and Data Mining, pages 597–605, 2012.
[15] S. Gregory. Local betweenness for finding communities in networks. Technical Report,
University of Bristol, 2008.
[16] J. Hopcroft, O. Khan, B. Kulis, and B. Selman. Natural communities in large linked networks.
In International Conference on Knowledge Discovery and Data Mining (SIGKDD),
pages 541–546, 2003.
[17] R. Kanawati. Community detection in social networks: the power of ensemble methods.
In International Conference on Data Science and Advanced Analytics (DSAA), 2014.
[18] R. R. Khorasgani, J. Chen, and O. R. Zaiane. Top leaders community detection approach in
information networks. In Workshop on Social Network Mining and Analysis (SNA-KDD),
pages 1–9, 2010.
[19] J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The
web as a graph: Measurements, models, and methods. In International Computing and
Combinatorics Conference, pages 1–18, 1999.
[20] V. Krebs. http://www.orgnet.com.
[21] A. Lancichinetti and S. Fortunato. Benchmarks for testing community detection algorithms
on directed and weighted graphs with overlapping communities. Physical Review
E, 80(016118), 2009.
[22] L. Lu and T. Zhou. Link prediction in complex networks: A survey. Physica A: Statistical
Mechanics and its Applications, 390(6):1150–1170, 2011.
[23] F. Luo and J. Z. Wang. Exploring local community structures in large networks. In
International Conference on Web Intelligence, pages 233–239, 2006.
[24] F. Moradi, T. Olovsson, and P. Tsigas. A local seed selection algorithm for overlapping
community detection. In International Conference on Advances in Social Networks Analysis
and Mining (ASONAM), pages 1–8, 2014.
[25] M. E. J. Newman. Detecting community structure in networks. The European Physical
Journal B, 38:321–330, 2004.
[26] M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical
Review E, 69(066113), 2004.
[27] M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks.
Physical Review E, 69(026113), 2004.
[28] S. Papadopoulos, Y. Kompatsiaris, and A. Vakali. A graph-based clustering scheme for
identifying related tags in folksonomies. In International Conference on Data Warehousing
and Knowledge Discovery, pages 65–76, 2010.
[29] M. A. Porter, J.-P. Onnela, and P. J. Mucha. Communities in networks. Notices of the
American Mathematical Society, 56(9):1082–1097, 2009.
[30] L. A. R. Guimera. Functional cartography of complex metabolic networks. Nature,
433(24):895–900, 2005.
[31] U. N. Raghavan, R. Albert, and S. Kumara. Near linear time algorithm to detect community
structures in large scale networks. Physical Review E, 76(036106), 2007.
[32] D. Shah and T. Zaman. Community detection in networks: The leader-follower algorithm.
In Workshop in Networks Across Disciplines in Theory and Applications (NIPS), pages
1–8, 2010.
[33] J. Shao, Z. Han, Q. Yang, and T. Zhou. Community detection based on distance dynamics.
In International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages
1075–1084, 2015.
[34] R. Sibson. Slink: an optimally efficient algorithm for the single-link cluster method. The
Computer Journal, 16:30–34, 1973.
[35] M. A. Tabarzad and A. Hamzeh. A heuristic local community detection method (hlcd).
Applied Intelligence, 2016(3217612), 2016.
[36] L. L. Tao, S. Bing, Y. Y. Xiang, and T. Fang. A local complex network communities’
discovery algorithm. In International Conference on Software Engineering and Service
Science (ICSESS), pages 787–790, 2013.
[37] C. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, and M. Tsiarli. Denser than the densest
subgraph: Extracting optimal quasi-cliques with quality guarantees. In International
Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 104–112, 2013.
[38] S. Wasserman and K. Faust. Social network analysis. Cambridge Univ. Press, Cambridge,
U.K., 1994.
[39] J. J. Whang, D. F. Gleich, and I. S. Dhillon. Licod: Leaders identification for community
detection in complex networks. In International Conference on Social Computing and
Networking (SocialCom), pages 577–582, 2011.
[40] J. J. Whang, D. F. Gleich, and I. S. Dhillon. Overlapping community detection using seed
set expansion. In International Conference on Conference on Information & Knowledge
Management (CIKM), pages 2099–2108, 2013.
[41] J. Yang and J. Leskovec. Defining and evaluating network communities based on groundtruth.
In International Conference on Data Mining (ICDM), pages 745–754, 2012.
[42] R. Yong-gong, S. Yu-qi, and L. Zhen. Community detection method based on local information.
In Computer Engineering, pages 12–24, 2011.
[43] T. Zhang and B.Wu. A method for local community detection by finding core nodes. In International
Conference on Advances in Social Networks Analysis and Mining (ASONAM),
pages 1171–1176, 2012.
[44] Y. Zhou, G. Sun, Y. Xing, R. Zhou, and Z. Wang. Local community detection algorithm
based on minimal cluster. Applied Computational Intelligence and Soft Computing, 46(1),
2017.