تشخیص انجمن در شبکه‌های پیچیده پویا مبتنی بر تعبیه گراف و خوشه‌بندی جمعی
الموضوعات :
مجید محمدپور
1
,
سیداکبر مصطفوی
2
,
وحید رنجبر
3
1 - دانشکده مهندسی کامپیوتر، دانشگاه یزد
2 - دانشکده مهندسی کامپیوتر، دانشگاه یزد
3 - دانشکده مهندسی کامپیوتر، دانشگاه یزد
الکلمات المفتاحية: تعبیه گراف, تشخیص انجمن, درجه پیمانه‌ای, خوشه‌بندی جمعی, شبکه پیچیده, یادگیر عمیق,
ملخص المقالة :
امروزه شبکه‌های پیچیده پویا به یکی از ارکان مهم زندگی بشر تبدیل شده‌اند و تشخیص انجمن در این شبکه‌ها یکی از مهم‌ترین مسائل در تحلیل آنها محسوب می‌شود. در این مقاله یک روش تشخیص انجمن مبتنی بر تعبیه گراف و روش یادگیری جمعی ارائه شده که می‌تواند درجه پیمانه‌ای‌بودن هر انجمن را حداکثر نماید. روش‌های تعبیه گراف یا یادگیری نمایش کم‌بعد از گره‌ها در گراف به علت قابلیت کاربردی گسترده آن در عملکرد شبکه‌های پیچیده پویا مانند تشخیص انجمن در شبکه، بسیار مورد توجه قرار گرفته‌اند. در این مقاله، یک روش تعبیه گراف پویا مبتنی بر یادگیر عمیق پیشنهاد شده که گراف خروجی از مرحله تعبیه گراف را به‌عنوان ورودی به مدل یادگیر جمعی می‌دهد تا با دقت قابل قبولی، انجمن‌ها را در شبکه تشخیص دهد. همچنین یک الگوریتم حریصانه جدید به نام پیوند جمع برای بهینه‌سازی تابع هدف برای مجموعه داده‌های مقیاس بزرگ در زمان بسیار کوتاه ارائه گردیده است. نشان داده شده که پارتیشن توافقی پیشنهادی نسبت به پارتیشن‌های به‌دست‌آمده از کاربرد مستقیم روش‌های خوشه‌بندی جمعی رایج، به ساختارهای خوشه‌ای واقعی نزدیک‌تر است. روش پیشنهادی به‌دلیل استفاده از روش پیش‌پردازش مبتنی بر تعبیه گراف پیشنهادی و همچنین استفاده از روش خوشه‌بندی جمعی، توانسته کارایی مناسبی را در مقایسه با سایر روش‌های رقیب از خود نشان دهد. نتایج تجربی آزمایش‌های انجام‌شده حاکی از برتری روش پیشنهادی در مقایسه با روش‌های رقیب است.
[1] Z. Gao, et al., "Hierarchical graph learning for protein–protein interaction," Nature Communications, vol. 14, Article ID: 1093, 2023.
[2] V. Ranjbar, M. Salehi, P. Jandaghi, and M. Jalili, "Qanet: tensor decomposition approach for query-based anomaly detection in heterogeneous information networks," IEEE Trans. on Knowledge and Data Engineering, vol. 31, no. 11, pp. 2178-2189, Nov. 2018.
[3] H. Dai, Y. Wang, R. Trivedi, and L. Song, Deep Coevolutionary Network: Embedding User and Item Features for Recommendation, arXiv:1609.03675v4, 2017
[4] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, "A comprehensive survey on graph neural networks," IEEE Trans. Neural Networks Learn. Syst., vol. 32, no. 1, pp. 4-24, Jan. 2021.
[5] J. Zhou, et al., "Graph neural networks: a review of methods and applications," AI Open, vol. 1, pp. 57-81, 2020.
[6] P. Xu, W. Hu, J. Wu, and B. Du, "Link prediction with signed latent factors in signed social networks," in Proc. 25th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining, pp. 1046-1054, Anchorage, AK, USA, 4-8 Aug. 2019.
[7] M. Khorasani, B. Minaei-Bidgoli, and C. Saedi, "Automatic synset extraction from text documents using a graph-based clustering approach via maximal cliques finding," International J. of Information and Communication Technology Research, vol. 11, no. 1, pp. 27-35, Winter 2019.
[8] A. Grover and J. Leskovec, "node2vec: scalable feature learning for networks," in Proc. of the 22nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 855-864, San Francisco, CA, USA, 13-17 Aug. 2016.
[9] J. Skarding, B. Gabrys, and K. Musial, "Foundations and modelling of dynamic networks using dynamic graph neural networks: a survey," IEEE Access, vol. 9, pp. 79143-79168, 2021.
[10] M. Torricelli, M. Karsai, and L. Gauvin, "weg2vec: event embedding for temporal networks," Scientific Reports, vol. 10, Article ID: 7164, 11 pp., 2020.
[11] S. Cao, W. Lu, and Q. Xu, "Deep neural networks for learning graph representations," in Proc. 13th AAAI Conf. on Artificial Intelligence, pp. 1145-1152, Phoenix, AZ, USA, 12-17 Feb. 2016.
[12] M. T. FaghihiNezhad and B. Minaei Bidgoli, "Development of an ensemble learning-based intelligent model for stock market forecasting," Scientia Iranica, vol. 28, no. 1, pp. 395-411, Jan./Feb. 2021.
[13] A. Banerjee, et al., "A new method for weighted ensemble clustering and coupled ensemble selection," Connection Science, vol. 33, no. 3, pp. 623-644, 2021.
[14] D. Huang, C. D. Wang, H. Peng, J. Lai, and C. K. Kwoh, "Enhanced ensemble clustering via fast propagation of cluster-wise similarities," IEEE Trans. on Systems, Man, and Cybernetics: Systems, vol. 51, no. 1, pp. 508-520, Jan. 2021.
[15] N. Ilc, "Weighted cluster ensemble based on partition relevance analysis with reduction step," IEEE Access, vol. 8, pp. 113720-113736, 2020.
[16] P. Goyal, A. Sapienza, and E. Ferrara, "Recommending teammates with deep neural networks," in Proc. 29th on Hypertext and Social Media, pp. 57-61, Baltimore, MD, USA, 9-12 Jul. 2018.
[17] J. B. Lee, R. Rossi, and X. Kong, "Graph classification using structural attention," in Proc. 24th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining, pp. 1666-1674, London, UK, 19-23 Aug. 2018.
[18] J. You, B. Liu, R. Ying, V. Pande, and J. Leskovec, "Graph convolutional policy network for goal-directed molecular graph generation," in Proc. 32nd Int. Conf. on Neural Information Processing Systems, pp. 6412-6422, Montréal, Canada, 3-8 Dec. 2018.
[19] R. Ying, J. You, C. Morris, X. Ren, W. L. Hamilton, and J. Leskovec, "Hierarchical graph representation learning with differentiable pooling," in Proc. 32nd Int. Conf. on Neural Information Processing Systems, 11 pp., Montréal, Canada, 3-8 Dec. 2018.
[20] Y. Ma, Z. Guo, Z. Ren, E. Zhao, J. Tang, and D. Yin, Streaming Graph Nneural Networks, arXiv preprint arXiv:1810.10627, 2018.
[21] F. Manessi, A. Rozza, and M. Manzo, Dynamic Graph Convolutional Networks, arXiv preprint arXiv:1704.06199, 2017.
[22] F. Monti, M. Bronstein, and X. Bresson, "Geometric matrix completion with recurrent multi-graph neural networks," in Proc. 31st Conf. on Neural Information Processing Systems, 11 pp., Long Beach, CA, USA, 4-9 Dec. 2017.
[23] J. You, R. Ying, X. Ren, W. Hamilton, and J. Leskovec, "GraphRNN: generating realistic graphs with deep auto-regressive models," in Proc. 35 th Int. Conf. on Machine Learning, 12 pp., Stockholm, Sweden, 10-15 Jul. 2018.
[24] Z. Zhang, A Note on Spectral Clustering and SVD of Graph Data, arXiv preprint arXiv:1809.11029, 2018.
[25] R. Ying, et al., "Graph convolutional neural networks for web-scale recommender systems," in Proc. 24th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining, pp. 974-983, London, UK, 19-23 Aug. 2018.
[26] D. Wang, P. Cui, and W. Zhu, "Structural deep network embedding," in Proc. 22th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining, pp. 1225-1234, San Francisco, CA, USA, 13-17 Aug. 2016.
[27] F. Manessi, A. Rozza, and M. Manzo, Dynamic Graph Convolutional Networks, arXiv preprint arXiv:1704.06199, 2017.
[28] Y. Ma, Z. Guo, Z. Ren, E. Zhao, J. Tang, and D. Yin, Streaming Graph Neural Networks, arXiv preprint arXiv:1810.10627, 2018.
[29] L. Zhu, D. Guo, J. Yin, G. Ver Steeg, and A. Galstyan, "Scalable temporal latent space inference for link prediction in dynamic social networks," IEEE Trans. on Knowledge and Data Engineering, vol. 28, no. 10, pp. 2765-2777, Oct. 2016.
[30] C. Hongyun, V. W. Zheng, and K. Chen-Chuan Chang, "A comprehensive survey of graph embedding: problems, techniques, and applications," IEEE Trans. on Knowledge and Data Engineering, vol. 3, no. 9, pp. 1616-1637, Sept. 2018.
[31] M. Ou, et al., "Asymmetric transitivity preserving graph embedding," in Proc. 22nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 1105-1114, San Francisco, CA, USA, 13-17 Aug. 2016.
[32] W. L. Hamilton, J. Leskovec, and D. Jurafsky, Diachronic Word Embeddings Reveal Statistical Laws of Semantic Change, arXiv preprint arXiv:1605.09096, 2016.
[33] S. Cao, W. Lu, and Q. Xu, "GraRep: learning graph representations with global structural information," in Proc. 21st Intl. Conf. on Knowledge Discovery and Data Mining, pp. 891-900, Melbourne Australia, 18-23 Oct. 2015.
[34] D. Wang, P. Cui, and W. Zhu, "Structural deep network embedding," in Proc. 22th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining, pp. 1225-1234, San Francisco, CA, USA, 13-17 Aug. 2016.
[35] A. L. Barabasi, Network Science, Cambridge University Press, 2016.
[36] K. Tu, P. Cui, X. Wang, P. S. Yu, and W. Zhu, "Deep recursive network embedding with regular equivalence," in Proc. 24th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining, pp. 2357-2366, London, UK, 19-23 Aug. 2018.
[37] A. Fred and A. K. Jain, "Combining multiple clusterings using evidence accumulation," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 27, no. 6, pp. 835-850, Jun. 2005.
[38] A. Strehl and J. Ghosh, "Cluster ensembles-a knowledge reuse framework for combining multiple partitions," J. of Machine Learning Research, vol. 3, pp. 583-617, 2002.
[39] H. Alizadeh, B. Minaei-Bidgoli, and H. Parvin, "Cluster ensemble selection based on a new cluster stability measure," Intelligent Data Analysis, vol. 18, no. 3, pp. 389-408, 2014.
[40] R. Caruana, et al., "Ensemble selection from libraries of models," in Proc. of the 21st Int. Conf. on Machine Learning, 9 pp., Banff, Canada, 4-8 Jul. 2004.
[41] X. Fern and W. Lin, "Cluster ensemble selection," Statistical Analysis and Data Mining, vol. 1, no. 3, pp. 128-141, Nov. 2008.
[42] J. Azimi and X. Fern, "Adaptive cluster ensemble selection," in Proc. of 21th Int. Joint Conf. on Artificial Intelligence, pp. 992-997, Pasadena, Ca, USA, 11-17 Jul. 2009.
[43] H. Alizadeh, P. H. Parvin, and S. Parvin, "A framework for cluster ensemble based on a max metric as cluster evaluator," IAENG International J. of Computer Science, vol. 39, no. 1, 10 pp., Feb. 2012.
[44] H. Alizadeh, B. Minaei-Bidgoli, and H. Parvin, "To improve the quality of cluster ensembles by selecting a subset of base clusters," J. of Experimental & Theoretical Artificial Intelligence, vol. 26, no. 1, Article ID: 813974, 2014.
[45] W., Li, Z. Wang, W. Sun, S. Bahrami, "An ensemble clustering framework based on hierarchical clustering ensemble selection and clusters clustering," Cybernetics and Systems, vol. 54, no. 5, pp. 741-766, 2023.
[46] H. Khalili, M. Rabbani, E. Akbari, "Clustering ensemble selection: a systematic mapping study," International Journal of Nonlinear Analysis and Applications, vol. 14, no. 9, pp. 209-240, 2023.
[47] S. T. Hadjitodorov, L. I. Kuncheva, and L. P. Todorova, "Moderate diversity for better cluster ensembles," Information Fusion, vol. 7, no. 3, pp. 264-275, Sept. 2006.
[48] H. Parvin, B. Minaei-Bidgoli, and H. Alizadeh, "A new clustering algorithm with the convergence proof," in Proc. of the 15th Int. Conf, on Knowledge-Based and Intelligent Information and Engineering Systems, vol. 1, pp. 21-31, Kaiserslautern, Germany, 12-14 Sept. 2011.
[49] V. Singh, L. Mukherjee, J. Peng, and J. Xu, "Ensemble clustering using semidefinite programming with applications," Mach. Learn., vol. 79, pp. 177-200, Dec. 2010.
[50] P. R. Rao and J. P. P. da Costa, "A performance study of a consensus clustering algorithm and properties of partition graph," in Proc. of IEEE Int. Conf. on Computational Intelligence and Computing Research, 5 pp., Coimbatore, India, 28-29 Dec. 2011.
[51] A. Gunoche, "Consensus of partitions: a constructive approach," Advances in Data Analysis and Classification, vol. 5, no. 3, pp. 215-229, 2011.
[52] I. T. Christou, "Coordination of cluster ensembles via exact methods," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 33, no. 2, pp. 279-293, Feb. 2011.
[53] S. Vega-Ponz and J. Ruiz-Shulcloper, "A survey of clustering ensemble algorithms," Int. J. of Pattern Recognition and Artificial Intelligence, vol. 25, no. 3, pp. 337-372, 2011.
[54] U. Brandes, et al., "On modularity clustering," IEEE Trans. on Knowledge and Data Engineering, vol. 20, no. 2, pp. 172-188, Feb. 2008.
[55] G. Agrawal and D. Kempe, "Modularity-maximizing network communities via mathematical programming," Eur. Phys. J. B, vol. 66, pp. 409-418, 2008.
[56] X. S. Zhang, et al., "Modularity optimization in community detection of complex networks," Europhys Lett, vol. 87, no. 3, Article ID: 38002, 2009.
[57] X. S. Zhang, et al., "A combinatorial model and algorithm for globally searching community structure in complex networks," J. Comb Optim, vol. 23, pp. 425-442, 2012.
[58] C. Zhao, et al., "Social network optimization for cluster ensemble selection," Fundamenta Informaticae, vol. 176, no. 1, pp. 79-102, 2020.
[59] R. Hosseinzadeh, H. Alizadeh, and E. Nazemi, "Community detection ensemble in social networks," in Proc. the 11th Iranian Conf. on Intelligent Systems, pp. 27-28, Tehran, Iran, Feb. 2013.
[60] D. Huang, C. D. Wang, and J. H. Lai, "Locally weighted ensemble clustering," IEEE Trans. on Cybernetics, vol. 48, no. 5, pp. 1460-1473, May 2018.
[61] P. Goyal, S. R. Chhetri, and A. Canedo, "dyngraph2vec: capturing network dynamics using dynamic graph representation learning," Knowledge-Based Systems, vol. 187, Article ID: 104816, Jan. 2020.
[62] P. Goyal, S. R. Chhetri, and A. Canedo, dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning, arXiv preprint arXiv:1809.02657, 2018.
[63] A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," Phys. Rev. E, vol. 70, Article ID: 066111 2004.
[64] M. E. J. Newman, "Modularity and community structure in networks," in Proc. Natl Acad. Sci. USA, vol. 103, no. 23, pp. 8577-8582, 6 Jun. 2006.
[65] L. Shuzhuo, C. Yinghui, H. Haifeng, and M. W. Feldman, "A genetic algorithm with local search strategy for improved detection of community structure," Complexity, vol. 15, no. 4, pp. 53-60, Mar./Apr. 2010.
[66] Y. Ren, C. Domeniconi, G. Zhang, and G. Yu, "Weighted-object ensemble clustering: methods and analysis," Knowledge and Information Systems, vol. 51, no. 2, pp. 661-689, 2017.
