社群偵測(community detection)是社會網路分析(social network analysis)所使用的一種方法之一，通過比對社群網路內實體之間的連線關係能找出網路當中看不到的隱性族群，能用已挖掘潛藏在數據背後所隱藏的重要訊息，在這近十年來，已受到各領域學者的關注。期間，亦有不少針對分群定義社群偵測的演算法不斷被學者提出。
在社群偵測演算法當中，本研究以Martelot與Hankin提出的快速品質塊膜度最佳化演算法(以下簡稱FMSm演算法)為基礎，提出強化特定網路節點關連之方法探討鄰接矩陣(adjacency matrix)修飾對FMSm演算法在社群偵測產生的影響。
在節點間鄰接關係之修飾中，本研究基於相同族群之節點會有高度關聯性之條件及過去文獻經常使用的隨機漫步法提出以共同好友集與PageRank方法從原始鄰接矩陣中萃取精煉矩陣，並與原始鄰接矩陣疊加之修飾演算法－F-FMSm與P-FMSm。經實驗結果證實，利用本研究所提出鄰接關係之修飾，能增加網路內部節點間相似關聯的差異性，使社群偵測演算法在判別節點所屬族群時，在分歧點差異較多之情況下將節點分至正確的族群當中。在標竿模型下量測，F-FMSm與P-FMSm在標竿網路樣本中最高可提升NMI (Normalized Mutual Information) 量值9.5%與6.2%，在非結合基因類型之演算法當中，此方法中有最優良的整體表現。

Community detection is one of the methods for social network analysis. By comparing the connections among entities in a social network, community detection discovers important messages hidden in the data. This method has become the focus of research in various fields for the past decade, during which time numerous algorithms for community definition and community detection have been proposed.

The community detection algorithm used in this study is based on the Fast Multi-Scale Detection algorithm (hereafter referred to as the FMSm algorithm) proposed by Martelot and Hankin, which enhances the association between specific network nodes, where the study investigated the effects of adjacency matrix modification in the FMSm algorithm.

In terms of node adjacency relationship modification, this study proposed using common friend set and PageRank method to extract refined matrix from original adjacency matrix and superpose the original adjacency matrix with modification algorithms F-FMSm and P-FMSm, based on the high association between nodes in the same community and the Random Walk method used in much past research. Results show that with the adjacency relationship modification proposed by this study, the difference in association between internal nodes in the network can be increased, so that when the community detection algorithm determines the community of a node, the node can be assigned to the correct community when there are more differences between branch points. When measured in the benchmark model, F-FMSm and P-FMSm can increase Normalized Mutual Information (NMI) by 9.5% and 6.2% respectively in benchmark network samples. With non-genetic algorithms, this method yielded the best overall performance.

[1] M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On Power-law Relationships of the Internet Topology,” in Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, New York, NY, USA, 1999, pp. 251–262.
[2] A.-L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, vol. 286, no. 5439, pp. 509–512, Oct. 1999.
[3] R. Albert, H. Jeong, and A.-L. Barabási, “Internet: Diameter of the World-Wide Web,” Nature, vol. 401, no. 6749, pp. 130–131, 9 1999.
[4] J. Leskovec and E. Horvitz, “Planetary-scale Views on a Large Instant-messaging Network,” in Proceedings of the 17th International Conference on World Wide Web, New York, NY, USA, 2008, pp. 915–924.
[5] R. Cazabet, M. Leguistin, and F. Amblard, “Automated Community Detection on Social Networks: Useful? Efficient? Asking the Users,” in Proceedings of the 4th International Workshop on Web Intelligence & Communities, New York, NY, USA, 2012, pp. 6:1–6:8.
[6] M. Salathé, M. Kazandjieva, J. W. Lee, P. Levis, M. W. Feldman, and J. H. Jones, “A high-resolution human contact network for infectious disease transmission,” Proc. Natl. Acad. Sci., vol. 107, no. 51, pp. 22020–22025, Dec. 2010.
[7] J.-C. Wang, C.-C. Chiu, and J. Tang, “The Correlation Study of eWOM and Product Sales Predictions Through SNA Perspectives: An Exploratory Investigation by Taiwan’s Cellular Phone Market,” in Proceedings of the 7th International Conference on Electronic Commerce, New York, NY, USA, 2005, pp. 666–673.
[8] R. Cross, S. P. Borgatti, and A. Parker, “Making Invisible Work Visible: Using Social Network Analysis to Support Strategic Collaboration,” Calif. Manage. Rev., vol. 44, no. 2, pp. 25–46, 2002.
[9] N. P. Nguyen, T. N. Dinh, S. Tokala, and M. T. Thai, “Overlapping Communities in Dynamic Networks: Their Detection and Mobile Applications,” in Proceedings of the 17th Annual International Conference on Mobile Computing and Networking, New York, NY, USA, 2011, pp. 85–96.
[10] P. Hui, E. Yoneki, S. Y. Chan, and J. Crowcroft, “Distributed Community Detection in Delay Tolerant Networks,” in Proceedings of 2Nd ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture, New York, NY, USA, 2007, pp. 7:1–7:8.
[11] B. H. Good, Y.-A. de Montjoye, and A. Clauset, “The performance of modularity maximization in practical contexts,” Phys. Rev. E, vol. 81, no. 4, Apr. 2010.
[12] A. Lancichinetti and S. Fortunato, “Limits of modularity maximization in community detection,” Phys. Rev. E, vol. 84, no. 6, Dec. 2011.
[13] C.-S. Chang, C.-Y. Hsu, J. Cheng, and D.-S. Lee, “A general probabilistic framework for detecting community structure in networks,” 2011, pp. 730–738.
[14] E. L. Martelot and C. Hankin, “Fast Multi-Scale Community Detection based on Local Criteria within a Multi-Threaded Algorithm,” ArXiv13010955 Phys., Jan. 2013.
[15] M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. E, vol. 69, no. 6, p. 066133, 18 2004.
[16] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. Stat. Mech. Theory Exp., vol. 2008, no. 10, p. P10008, Oct. 2008.
[17] L. Ma, M. Gong, J. Liu, Q. Cai, and L. Jiao, “Multi-level learning based memetic algorithm for community detection,” Appl. Soft Comput., vol. 19, pp. 121–133, 2014.
[18] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci., vol. 99, no. 12, pp. 7821–7826, Jun. 2002.
[19] E. A. Leicht and M. E. J. Newman, “Community structure in directed networks,” Phys. Rev. Lett., vol. 100, no. 11, Mar. 2008.
[20] F. D. Malliaros and M. Vazirgiannis, “Clustering and Community Detection in Directed Networks: A Survey,” ArXiv13080971 Phys., Aug. 2013.
[21] M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proc. Natl. Acad. Sci., vol. 105, no. 4, pp. 1118–1123, Jan. 2008.
[22] “Yeh, Ying-Ling， ‘On the proximity for community detection,’ Thesis, National Taipei University Department of Statistics.” .
[23] A. Lancichinetti and S. Fortunato, “Community detection algorithms: A comparative analysis,” Phys. Rev. E, vol. 80, no. 5, p. 056117, 30 2009.
[24] J. Huang, H. Sun, Y. Liu, Q. Song, and T. Weninger, “Towards Online Multiresolution Community Detection in Large-Scale Networks,” PLoS ONE, vol. 6, no. 8, p. e23829, 24 2011.
[25] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data Clustering: A Review,” ACM Comput Surv, vol. 31, no. 3, pp. 264–323, 1999.
[26] M. A. Porter, J.-P. Onnela, and P. J. Mucha, “Communities in Networks,” ArXiv09023788 Cond-Mat Physicsphysics Stat, Feb. 2009.
[27] J. Yang and J. Leskovec, “Community-Affiliation Graph Model for Overlapping Network Community Detection,” in 2012 IEEE 12th International Conference on Data Mining (ICDM), 2012, pp. 1170–1175.
[28] S. Fortunato, “Community detection in graphs,” Phys. Rep., vol. 486, no. 3–5, pp. 75–174, Feb. 2010.
[29] 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, Jul. 2009.
[30] W. W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” J. Anthropol. Res., vol. 33, no. 4, pp. 452–473, Spring 1977.
[31] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations,” Behav. Ecol. Sociobiol., vol. 54, no. 4, pp. 396–405, Jun. 2003.
[32] M. E. J. Newman, “Modularity and community structure in networks,” Proc. Natl. Acad. Sci., vol. 103, no. 23, pp. 8577–8582, Jun. 2006.
[33] P. M. Gleiser and L. Danon, “Community structure in jazz,” Adv. Complex Syst., vol. 06, no. 04, pp. 565–573, Spring 2003.
[34] J. Duch and A. Arenas, “Community detection in complex networks using extremal optimization,” Phys. Rev. E, vol. 72, no. 2, p. 027104, 24 2005.
[35] R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas, “Self-similar community structure in a network of human interactions,” Phys. Rev. E, vol. 68, no. 6, p. 065103, 17 2003.
[36] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442, Winter 1998.
[37] “V. Batagelj, M. Zaverˇsnik, Pajek datasets, 2002, available at http://vlado.fmf.uni-lj.si/pub/networks/data/collab/geom.” .
[38] J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graph Evolution: Densification and Shrinking Diameters,” ACM Trans Knowl Discov Data, vol. 1, no. 1, 2007.
[39] M. Boguñá, R. Pastor-Satorras, A. Díaz-Guilera, and A. Arenas, “Models of social networks based on social distance attachment,” Phys. Rev. E, vol. 70, no. 5, p. 056122, 22 2004.