網路分析的領域中，大規模網路是不容易有效率地進行分析以及視覺化的，使用網路縮減技術與找出群集的網路分群能夠有效的幫助理解網路中的資訊。而除了計算效率之外，網路縮減與網路分群的領域各自獨立，結合兩個領域一同進行探討的研究並不多見。本研究提出一結合兩種社群分析技術的框架進行實驗，以機率分配的形式取代定值的數值，搭配KS統計量作為衡量網路差距的指標，比較爬蟲式的縮減演算法與基因演算法的計算效率與性能，再設計一實驗套用不同的實驗框架探討網路縮減與分群的交互效應。為了確保實驗結果不受特定規模或特性的資料集影響，本研究收集了20組不同規模與結構特性的無向網路資料集，並採用正規化抽樣函數來對所有縮減比例的性能表現都進行試驗，並將不同比例的性能指標繪製為曲線並計算曲線下面積作為性能綜合指標，對每組資料集與演算法的組合重複進行50次試驗並以二因子變異數分析 (two-way ANOVA) 進行統計檢定。研究結果顯示出，網路分群的方法與網路縮減的方法彼此之間為獨立的因子，彼此並無顯著交互效應。而在大規模網路的縮減運算中，結合分群與縮減的方法可以在相同的性能表現下，平均節省30%的計算時間。

In the field of network analysis, large-scale networks are not easy to analyze and visualize. Therefore, network reduction and clustering are important to help understand the information in the network. In addition to computational efficiency, the fields of network reduction and network clustering are independent, and there are few studies that combine the two fields. This study proposed a framework that combines two community analysis techniques and conduct experiments, which use probability distribution and the KS-statistic as an indicator to measure the network gap. And compares the computing performance of several methods with the crawl-based reduction method. Then a different experiment is designed to investigate the interactive effect of network reduction and clustering. In order to ensure that results are not affected by specific data size or characteristic, this study collected 20 datasets of undirected networks of different scales and structural features. The performance indicators were plotted as a curve and the area under the curve was calculated as a comprehensive metric. The combination of each data set and algorithm was conducted 50 times and statistically tested by two-way ANOVA. The results show that the method of network clustering and the method of network reduction are independent factors. Furthermore, in large-scale network reduction, the method of combining clustering and then reducing can obtain an average of 30% computing time savings under the same performance.

[1] S. P. Borgatti, A. Mehra, D. J. Brass, and G. Labianca, "Network analysis in the social sciences," Science, vol. 323, no. 5916, pp. 892-895, 13 Feb 2009.
[2] O. Serrat, "Social network analysis," in Knowledge solutions: Springer, 2017, pp. 39-43.
[3] S. Wasserman and K. Faust, Social network analysis: Methods and applications. June 2012: Cambridge University Press, 1994.
[4] D. Watts, "Networks, dynamics, and the small-world phenomenon," American Journal of sociology, vol. 105, no. 2, pp. 493-527, September 1999.
[5] D. R. White, J. Owen-Smith, J. Moody, and W. W. Powell, "Networks, fields and organizations: micro-dynamics, scale and cohesive embeddings," Computational mathematical organization theory, vol. 10, no. 1, pp. 95-117, 2004.
[6] E. L. Kick, L. A. McKinney, S. McDonald, and A. Jorgenson, "A multiple-network analysis of the world system of nations, 1995-1999," Sage handbook of social network analysis, pp. 311-327, 2011.
[7] A. Quan-Haase and B. Wellman, Computer-mediated community in a high-tech organization (The firm as a collaborative community: reconstructing trust in the knowledge economy). 2006, pp. 281-333.
[8] J. A. Barnes and F. Harary, "Graph theory in network analysis," Social networks, vol. 5, no. 2, pp. 235-244, June 1983.
[9] F. Harary and R. Z. Norman, Graph theory as a mathematical model in social science (no. 2). University of Michigan, Institute for Social Research Ann Arbor, 1953.
[10] J. L. Moreno, Who shall survive? Foundations of sociometry, group psychotherapy and socio-drama. 1953.
[11] F. Zhou, S. Malher, and H. Toivonen, "Network simplification with minimal loss of connectivity," in 2010 IEEE international conference on data mining, 2010, pp. 659-668: IEEE.
[12] H. Oh, "Aggregation of buses for a network reduction," IEEE Transactions on Power Systems, vol. 27, no. 2, pp. 705-712, 09 January 2012.
[13] D. Zhang, J. Yin, X. Zhu, and C. Zhang, "Network representation learning: A survey," IEEE transactions on Big Data, vol. 6, no. 1, pp. 3-28, 1 March 2018.
[14] S. Arrami, W. Oueslati, and J. Akaichi, "Detection of opinion leaders in social networks: a survey," in International conference on intelligent interactive multimedia systems and services, 2018, pp. 362-370: Springer.
[15] Y. Liu, T. Safavi, A. Dighe, and D. Koutra, "Graph summarization methods and applications: A survey," ACM computing surveys, vol. 51, no. 3, pp. 1-34, 22 June 2018.
[16] C. Bhaumik, A. K. Agrawal, and P. Sinha, "Using social network graphs for search space reduction in internet of things," in Proceedings of the 2012 ACM Conference on Ubiquitous Computing, 2012, pp. 602-603.
[17] L. Bo-Seng, "Metaheuristic-based Optimization for Data Sampling of Social Network Clusters," Master, Department of Industrial Engineering and Management, National Taiwan University of Sciece and Technology, 2021.
[18] A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509-512, 15 October 1999.
[19] M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the internet topology," ACM SIGCOMM computer communication review, vol. 29, no. 4, pp. 251-262, 30 August 1999.
[20] S. Milgram, "The small world problem," Psychology today, vol. 2, no. 1, pp. 60-67, 1 May 1967.
[21] R. Albert, H. Jeong, and A.-L. Barabási, "Diameter of the world-wide web," Nature, vol. 401, no. 6749, pp. 130-131, 09 September 1999.
[22] 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, 2008, pp. 915-924.
[23] M. Plantié and M. Crampes, "Survey on social community detection," in Social media retrieval: Springer, 2013, pp. 65-85.
[24] B. Krishnamurthy and J. Wang, "On network-aware clustering of web clients," in Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2000, pp. 97-110.
[25] P. K. Reddy, M. Kitsuregawa, P. Sreekanth, and S. S. Rao, "A graph based approach to extract a neighborhood customer community for collaborative filtering," in International Workshop on Databases in Networked Information Systems, 2002, pp. 188-200: Springer.
[26] K. Reddy, M. Kitsuregawa, P. Sreekanth, and S. Rao, "In DNIS'02: Proceedings of the Second International Workshop on Databases in Networked Information Systems," ed. London, UK: Springer-Verlag, 2002.
[27] K. Steinhaeuser, N. V. Chawla, and A. R. Ganguly, "Complex networks as a unified framework for descriptive analysis and predictive modeling in climate science," Statistical Analysis and Data Mining: The ASA Data Science Journal, vol. 4, no. 5, pp. 497-511, 16 December 2011.
[28] R. Agrawal and H. Jagadish, "Algorithms for searching massive graphs," IEEE Transactions on Knowledge and Data Engineering, vol. 6, no. 2, pp. 225-238, 1 April 1994.
[29] B. Adamcsek, G. Palla, I. J. Farkas, I. Derényi, and T. Vicsek, "CFinder: locating cliques and overlapping modules in biological networks," Bioinformatics, vol. 22, no. 8, pp. 1021-1023, 15 April 2006.
[30] F. D. Malliaros and M. Vazirgiannis, "Clustering and community detection in directed networks: A survey," Physics reports, vol. 533, no. 4, pp. 95-142, 30 December 2013.
[31] S. Fortunato, "Community detection in graphs," Physics reports, vol. 486, no. 3-5, pp. 75-174, 17 November 2010.
[32] M. Coscia, F. Giannotti, and D. Pedreschi, "A classification for community discovery methods in complex networks," Statistical Analysis and Data Mining: The ASA Data Science Journal, vol. 4, no. 5, pp. 512-546, 09 September 2011.
[33] M. Crampes and M. Plantié, "A unified community detection, visualization and analysis method," Advances in complex systems, vol. 17, no. 01, p. 1450001, 12 March 2014.
[34] J. MacQueen, "Classification and analysis of multivariate observations," in 5th Berkeley Symp. Math. Statist. Probability, 1967, pp. 281-297.
[35] K. Nordhausen, "The elements of statistical learning: data mining, inference, and prediction, by Trevor Hastie, Robert Tibshirani, Jerome Friedman," ed: Wiley Online Library, 2009.
[36] U. Brandes, M. Gaertler, and D. Wagner, "Experiments on graph clustering algorithms," in European symposium on algorithms, 2003, pp. 568-579: Springer.
[37] A. Clauset, M. E. Newman, and C. Moore, "Finding community structure in very large networks," Physical review E, vol. 70, no. 6, p. 066111, 6 December 2004.
[38] A. Pothen, H. D. Simon, and K.-P. Liou, "Partitioning sparse matrices with eigenvectors of graphs," SIAM journal on matrix analysis and applications, vol. 11, no. 3, pp. 430-452, 15 August 1990.
[39] B. D. Hughes, Random walks and random environments: random walks. Oxford University Press, 1995.
[40] F.-Y. Wu, "The potts model," Reviews of modern physics, vol. 54, no. 1, p. 235, 1 January 1982.
[41] M. A. Porter, J.-P. Onnela, and P. J. Mucha, "Communities in networks," Notices of the AMS, vol. 56, no. 9, pp. 1082-1097, October 2009.
[42] G. Palla, I. Derényi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," Nature, vol. 435, no. 7043, pp. 814-818, 09 Hune 2005.
[43] M. E. Newman, "Fast algorithm for detecting community structure in networks," Physical review E, vol. 69, no. 6, p. 066133, 18 June 2004.
[44] M. Hoffman, D. Steinley, K. M. Gates, M. J. Prinstein, and M. J. Brusco, "Detecting clusters/communities in social networks," Multivariate behavioral research, vol. 53, no. 1, pp. 57-73, 08 December 2018.
[45] U. N. Raghavan, R. Albert, and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Physical review E, vol. 76, no. 3, p. 036106, 11 September 2007.
[46] M. E. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical review E, vol. 74, no. 3, p. 036104, 11 September 2006.
[47] J. Reichardt and S. Bornholdt, "Statistical mechanics of community detection," Physical review E, vol. 74, no. 1, p. 016110, 18 July 2006.
[48] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," Journal of statistical mechanics: theory experiment, vol. 2008, no. 10, p. P10008, 9 October 2008.
[49] V. A. Traag, L. Waltman, and N. J. Van Eck, "From Louvain to Leiden: guaranteeing well-connected communities," Scientific reports, vol. 9, no. 1, pp. 1-12, 26 March 2019.
[50] G. A. Pagani and M. Aiello, "The power grid as a complex network: a survey," Physica A: Statistical Mechanics its Applications, vol. 392, no. 11, pp. 2688-2700, 10 January 2013.
[51] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, "The large-scale organization of metabolic networks," Nature, vol. 407, no. 6804, pp. 651-654, 05 October 2000.
[52] J. P. Doye, "Network topology of a potential energy landscape: A static scale-free network," Physical review letters, vol. 88, no. 23, p. 238701, 23 January 2002.
[53] J. Travers and S. Milgram, "An experimental study of the small world problem," in Social networks: Elsevier, 1977, pp. 179-197.
[54] W. Aiello, F. Chung, and L. Lu, "A random graph model for massive graphs," in Proceedings of the thirty-second annual ACM symposium on Theory of computing, 2000, pp. 171-180.
[55] V. Colizza, A. Barrat, M. Barthélemy, and A. Vespignani, "Predictability and epidemic pathways in global outbreaks of infectious diseases: the SARS case study," BMC medicine, vol. 5, no. 1, pp. 1-13, 21 November 2007.
[56] R. Guimera and L. A. N. Amaral, "Modeling the world-wide airport network," The European Physical Journal B, vol. 38, no. 2, pp. 381-385, 01 March 2004.
[57] M. Boss, H. Elsinger, M. Summer, and S. Thurner 4, "Network topology of the interbank market," Quantitative finance, vol. 4, no. 6, pp. 677-684, 18 Aug 2004.
[58] S. M. Ashraf, B. Rathore, and S. Chakrabarti, "Performance analysis of static network reduction methods commonly used in power systems," in 2014 Eighteenth National Power Systems Conference (NPSC), 2014, pp. 1-6: IEEE.
[59] V. Dubois and C. Bothorel, "Transitive reduction for social network analysis and visualization," in The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05), 2005, pp. 128-131: IEEE.
[60] M. Kudelka, Z. Horak, V. Snasel, and A. Abraham, "Social network reduction based on stability," in 2010 International Conference on Computational Aspects of Social Networks, 2010, pp. 509-514: IEEE.
[61] J. G. Zañudo and R. Albert, "An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks," Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 23, no. 2, p. 025111, 22 May 2013.
[62] A. Nagarajan and R. Ayyanar, "Application of minimum spanning tree algorithm for network reduction of distribution systems," in 2014 North American Power Symposium (NAPS), 2014, pp. 1-5: IEEE.
[63] A. Nagarajan et al., "Network reduction algorithm for developing distribution feeders for real-time simulators," in 2017 IEEE Power & Energy Society General Meeting, 2017, pp. 1-5: IEEE.
[64] S. Tsugawa and H. Ohsaki, "Benefits of bias in crawl-based network sampling for identifying key node set," IEEE Access, vol. 8, pp. 75370-75380, 20 April 2020.
[65] N. Martin, P. Frasca, and C. Canudas-de-Wit, "Large-scale network reduction towards scale-free structure," IEEE Transactions on Network Science Engineering, vol. 6, no. 4, pp. 711-723, 26 September 2018.
[66] H. A. Beni and A. Bouyer, "TI-SC: top-k influential nodes selection based on community detection and scoring criteria in social networks," Journal of Ambient Intelligence
Humanized Computing, vol. 11, no. 11, pp. 4889-4908, 11 February 2020.
[67] M. M. Deza and E. Deza, "Voronoi diagram distances," in Encyclopedia of Distances: Springer, 2013, pp. 339-347.
[68] Y. Bai, H. Ding, S. Bian, T. Chen, Y. Sun, and W. Wang, "Simgnn: A neural network approach to fast graph similarity computation," in Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, 2019, pp. 384-392.
[69] R. Albert and A.-L. Barabási, "Statistical mechanics of complex networks," Reviews of modern physics, vol. 74, no. 1, p. 47, 30 January 2002.
[70] P. N. Krivitsky, M. S. Handcock, A. E. Raftery, and P. D. Hoff, "Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models," Social networks, vol. 31, no. 3, pp. 204-213, 26 May 2009.
[71] M. Ghavipour and M. R. Meybodi, "Irregular cellular learning automata-based algorithm for sampling social networks," Engineering Applications of Artificial Intelligence, vol. 59, pp. 244-259, 14 January 2017.
[72] A. Rezvanian, B. Moradabadi, M. Ghavipour, M. M. D. Khomami, and M. R. Meybodi, Learning automata approach for social networks (Studies in Computational Intelligence). Springer, 2019.
[73] M. L. Goldstein, S. A. Morris, and G. G. Yen, "Problems with fitting to the power-law distribution," The European Physical Journal B-Condensed Matter
Complex Systems, vol. 41, no. 2, pp. 255-258, 18 June 2004.
[74] H. Xu et al., "Graph partitioning and graph neural network based hierarchical graph matching for graph similarity computation," Neurocomputing, vol. 439, pp. 348-362, 7 June 2021.
[75] D. J. Watts and S. H. Strogatz, "Collective dynamics of ‘small-world’networks," Nature, vol. 393, no. 6684, pp. 440-442, 04 June 1998.
[76] M. Newman, "Networks: An introduction," Artif. Life, vol. 18, pp. 241-2, 1 April 2012.
[77] S. Wang, L. Huang, C.-H. Hsu, and F. Yang, "Collaboration reputation for trustworthy Web service selection in social networks," Journal of Computer System Sciences, vol. 82, no. 1, pp. 130-143, 2016.
[78] Y.-X. Kong, G.-Y. Shi, R.-J. Wu, and Y.-C. Zhang, "k-core: Theories and applications," Physics Reports, vol. 832, pp. 1-32, 23 November 2019.
[79] S. B. Seidman, "Network structure and minimum degree," Social networks, vol. 5, no. 3, pp. 269-287, September 1983.
[80] Q. Yu, H. Shao, and Z. Duan, "Research groups of oncology co-authorship network in China," Scientometrics, vol. 89, no. 2, pp. 553-567, 06 August 2011.
[81] J. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani, "Large scale networks fingerprinting and visualization using the k-core decomposition," Advances in neural information processing systems, vol. 18, 05 December 2005.
[82] K. J. Dooley, S. D. Pathak, T. J. Kull, Z. Wu, J. Johnson, and E. Rabinovich, "Process network modularity, commonality, and greenhouse gas emissions," Journal of Operations Management, vol. 65, no. 2, pp. 93-113, 18 March 2019.
[83] P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti, "Generalized louvain method for community detection in large networks," in 2011 11th international conference on intelligent systems design and applications, 2011, pp. 88-93: IEEE.
[84] V. A. Traag, "Faster unfolding of communities: Speeding up the Louvain algorithm," Physical Review E, vol. 92, no. 3, p. 032801, 3 September 2015.
[85] J. Leskovec and C. Faloutsos, "Sampling from large graphs," in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006, pp. 631-636.
[86] F. Gehring and P. Halmos, Graph Theory (Graduate Texts in Mathematics).
[87] N. Ahmed, J. Neville, and R. R. Kompella, "Network sampling via edge-based node selection with graph induction," Department of Computer Science Technical Reports, January 2011.
[88] J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press, 1992.
[89] P. Chunaev, "Community detection in node-attributed social networks: a survey," Computer Science Review, vol. 37, p. 100286, 21 July 2020.
[90] L. Waltman and N. J. Van Eck, "A smart local moving algorithm for large-scale modularity-based community detection," The European physical journal B, vol. 86, no. 11, pp. 1-14, 13 November 2013.
[91] J. Duch and A. Arenas, "Community detection in complex networks using extremal optimization," Physical review E, vol. 72, no. 2, p. 027104, 24 August 2005.
[92] H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich, "Local higher-order graph clustering," in Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, 2017, pp. 555-564.
[93] C. R. Myers, "Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs," Physical review E, vol. 68, no. 4, p. 046116, 20 Octobor 2003.
[94] J. M. Urquiza et al., "Using machine learning techniques and genomic/proteomic information from known databases for defining relevant features for PPI classification," Computers in biology medicine, vol. 42, no. 6, pp. 639-650, 8 May 2012.
[95] V. Colizza, R. Pastor-Satorras, and A. Vespignani, "Reaction–diffusion processes and metapopulation models in heterogeneous networks," Nature Physics, vol. 3, no. 4, pp. 276-282, 04 March 2007.
[96] S. Kumar, F. Spezzano, V. Subrahmanian, and C. Faloutsos, "Edge weight prediction in weighted signed networks," in 2016 IEEE 16th International Conference on Data Mining (ICDM), 2016, pp. 221-230: IEEE.
[97] J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graph evolution: Densification and shrinking diameters," ACM transactions on Knowledge Discovery from Data, vol. 1, no. 1, pp. 2-es, 01 March 2007.
[98] A. L. Traud, P. J. Mucha, and M. A. Porter, "Social structure of facebook networks," Physica A: Statistical Mechanics its Applications, vol. 391, no. 16, pp. 4165-4180, 15 August 2012.
[99] B. Rozemberczki, C. Allen, and R. Sarkar, "Multi-scale attributed node embedding," Journal of Complex Networks, vol. 9, no. 2, p. cnab014, 07 May 2021.