• الصفحة الرئيسية
  • تشخیص انجمن در شبکه‌های پیچیده پویا مبتنی بر تعبیه گراف و خوشه‌بندی جمعی

شارک

عنوان URL للمقالة


رقم المقالة : 1401022837404 زيارة : 2140 الصفحة: 141 - 157

نوع المخطوط: المحکّمة

تشخیص انجمن در شبکه‌های پیچیده پویا مبتنی بر تعبیه گراف و خوشه‌بندی جمعی

الموضوعات :

مجید محمدپور 1 , سیداکبر مصطفوی 2 , وحید رنجبر 3

1 - دانشکده مهندسی کامپیوتر، دانشگاه یزد
2 - دانشکده مهندسی کامپیوتر، دانشگاه یزد
3 - دانشکده مهندسی کامپیوتر، دانشگاه یزد

تاريخ الإرسال : 18 الخميس , شوال, 1443 تاريخ التأكيد : 05 السبت , شعبان, 1444 تاريخ الإصدار : 10 الثلاثاء , شعبان, 1445

الکلمات المفتاحية: تعبیه گراف, تشخیص انجمن, درجه پیمانه‌ای, خوشه‌بندی جمعی, شبکه پیچیده, یادگیر عمیق,

ملخص المقالة :

امروزه شبکه‌های پیچیده پویا به یکی از ارکان مهم زندگی بشر تبدیل شده‌اند و تشخیص انجمن در این شبکه‌ها یکی از مهم‌ترین مسائل در تحلیل آنها محسوب می‌شود. در این مقاله یک روش تشخیص انجمن مبتنی بر تعبیه گراف و روش یادگیری جمعی ارائه شده که می‌تواند درجه پیمانه‌ای‌بودن هر انجمن را حداکثر نماید. روش‌های تعبیه گراف یا یادگیری نمایش کم‌بعد از گره‌ها در گراف به علت قابلیت کاربردی گسترده آن در عملکرد شبکه‌های پیچیده پویا مانند تشخیص انجمن در شبکه، بسیار مورد توجه قرار گرفته‌اند. در این مقاله، یک روش تعبیه گراف پویا مبتنی بر یادگیر عمیق پیشنهاد شده که گراف خروجی از مرحله تعبیه گراف را به‌عنوان ورودی به مدل یادگیر جمعی می‌دهد تا با دقت قابل قبولی، انجمن‌ها را در شبکه تشخیص دهد. همچنین یک الگوریتم حریصانه جدید به نام پیوند جمع برای بهینه‌سازی تابع هدف برای مجموعه داده‌های مقیاس بزرگ در زمان بسیار کوتاه ارائه گردیده است. نشان داده شده که پارتیشن توافقی پیشنهادی نسبت به پارتیشن‌های به‌دست‌آمده از کاربرد مستقیم روش‌های خوشه‌بندی جمعی رایج، به ساختارهای خوشه‌ای واقعی نزدیک‌تر است. روش پیشنهادی به‌دلیل استفاده از روش پیش‌پردازش مبتنی بر تعبیه گراف پیشنهادی و همچنین استفاده از روش خوشه‌بندی جمعی، توانسته کارایی مناسبی را در مقایسه با سایر روش‌های رقیب از خود نشان دهد. نتایج تجربی آزمایش‌های انجام‌شده حاکی از برتری روش پیشنهادی در مقایسه با روش‌های رقیب است.

المصادر:

[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.
نص كامل:
معرفي يک روش جديد خوشه‌يابي خودکار

نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 21، شماره 3، پاییز 1402  141

مقاله پژوهشی

تشخیص انجمن در شبکه‌های پیچیده پویا مبتنی بر 
تعبیه گراف و خوشه‌بندی جمعی

مجید محمدپور، سیداکبر مصطفوی و وحید رنجبر

 

 

1 

چکیده: امروزه شبکه‌های پیچیده پویا به یکی از ارکان مهم زندگی بشر تبدیل شده‌اند و تشخیص انجمن در این شبکه‌ها یکی از مهم‌ترین مسائل در تحلیل آنها محسوب می‌شود. در این مقاله یک روش تشخیص انجمن مبتنی بر تعبیه گراف و روش یادگیری جمعی ارائه شده که می‌تواند درجه پیمانه‌ای‌بودن هر انجمن را حداکثر نماید. روش‌های تعبیه گراف یا یادگیری نمایش کم‌بعد از گره‌ها در گراف به علت قابلیت کاربردی گسترده آن در عملکرد شبکه‌های پیچیده پویا مانند تشخیص انجمن در شبکه، بسیار مورد توجه قرار گرفته‌اند. در این مقاله، یک روش تعبیه گراف پویا مبتنی بر یادگیر عمیق پیشنهاد شده که گراف خروجی از مرحله تعبیه گراف را به‌عنوان ورودی به مدل یادگیر جمعی می‌دهد تا با دقت قابل قبولی، انجمن‌ها را در شبکه تشخیص دهد. همچنین یک الگوریتم حریصانه جدید به نام پیوند جمع برای بهینه‌سازی تابع هدف برای مجموعه داده‌های مقیاس بزرگ در زمان بسیار کوتاه ارائه گردیده است. نشان داده شده که پارتیشن توافقی پیشنهادی نسبت به پارتیشن‌های به‌دست‌آمده از کاربرد مستقیم روش‌های خوشه‌بندی جمعی رایج، به ساختارهای خوشه‌ای واقعی نزدیک‌تر است. روش پیشنهادی به‌دلیل استفاده از روش پیش‌پردازش مبتنی بر تعبیه گراف پیشنهادی و همچنین استفاده از روش خوشه‌بندی جمعی، توانسته کارایی مناسبی را در مقایسه با سایر روش‌های رقیب از خود نشان دهد. نتایج تجربی آزمایش‌های انجام‌شده حاکی از برتری روش پیشنهادی در مقایسه با روش‌های رقیب است.

 

کلیدواژه: تعبیه گراف، تشخیص انجمن، درجه پیمانه‌ای، خوشه‌بندی جمعی، شبکه پیچیده، یادگیر عمیق.

1-       مقدمه

اخیراً تحلیل گراف به دلیل فراگیری شبکه‌ها در دنیای واقعی، توجه فزاینده‌ای را به خود جلب کرده است. گراف‌ها (شبکه‌ها) برای نشان‌دادن اطلاعات در حوزه‌های مختلف مثل زیست‌شناسی (شبکه‌های برهم‌کنش پروتئین- پروتئین)، علوم اجتماعی (شبکه‌های دوست‌یابی) و زبان‌شناسی استفاده می‌شوند [1] تا [3]. مدل‌سازی تعاملات بین گراف‌ها، محققان را قادر ساخته تا سیستم‌های مختلف تحت شبکه را به‌صورت مجموعه‌ای از موجودیت‌های سیستمی درک کنند [3]. مثلاً شبکه‌های اجتماعی برای برنامه‌های کاربردی مانند دوست‌یابی یا توصیه محتوا و نیز برای تبلیغ مورد استفاده قرار گرفته‌اند. وظایف تحلیل گراف را می‌توان به‌طور گسترده به چهار دسته تقسیم کرد: طبقه‌بندی گره [4] و [5]، پیش‌بینی لینک [6]، خوشه‌بندی [7] و مصورسازی [8]. هدف طبقه‌بندی گره، مشخص‌کردن برچسب گره‌ها (رأس‌ها) بر پایه سایر گره‌های برچسب‌گذاری‌شده و توپولوژی شبکه است. پیش‌بینی لینک به وظیفه پیش‌بینی لینک یا لینک‌هایی که احتمالاً در آینده رخ می‌دهند، اشاره دارد. خوشه‌بندی برای پیداکردن زیرمجموعه‌هایی از گره‌های مشابه مورد استفاده قرار می‌گیرد و نهایتاً مصورسازی به فراهم‌کردن بینش‌هایی درباره ساختار شبکه کمک می‌کند. شبکه پویای پیچیده2 به شبکه‌ای با مقیاس بالا گفته می‌شود که دارای ساختارهای توپولوژی پیچیده و رفتارهای پویاست که در گذر زمان تغییر می‌کند [9]. محققان در رشته‌های مختلف سعی کرده‌اند تا سیستمی را که بر روی آن کار می‌کنند بر ساختار شبکه‌های پیچیده منطبق سازند. با استفاده از مشخصات و ابزارهایی که در زمینه شبکه‌های پیچیده وجود دارند به‌راحتی می‌توان سیستم را مدل نمود [10]؛ مثلاً‌ می‌توان به شبکه‌های زیستی، شبکه‌های ارتباطی، شبکه‌های اجتماعی و شبکه‌های بیماری‌های همه‌گیر اشاره کرد. در ابتدا مهم‌ترین هدف استفاده از شبکه‌های پیچیده، تحلیل رفتارهای نهفته در سیستم‌های مورد استفاده محققان در رشته‌های مختلف بود. با استفاده از امکاناتی که علم شبکه‌های پیچیده در اختیار محققان قرار می‌داد این امکان فراهم شد تا بتوانند تحلیل‌های دقیق و مفیدی را بر روی شبکه‌های مورد استفاده در زمینه‌های مختلف علمی داشته باشند. از جمله مهم‌ترین کارهایی که اخیراً محققین در حوزه شبکه‌های پیچیده پویا انجام داده‌اند، کاهش ابعاد شبکه با روش‌های تعبیه گراف3 بوده است. تعبیه گراف می‌تواند شبکه را از فضای بزرگی به فضای کوچک‌تری تعبیه کند؛ بدون اینکه به ساختار گراف اصلی صدمه‌ای وارد شود و بنابراین این تعبیه گراف را می‌توان یکی از مهم‌ترین مراحل در پیش‌پردازش شبکه‌های پیچیده پویا در نظر گرفت. اگر هدف تشخیص انجمن‌ها4 در شبکه پیچیده باشد، مرحله تعبیه گراف را می‌توان به‌عنوان ورودی مدل برای تشخیص انجمن‌ها در نظر گرفت. از این رو تعبیه گراف نهایتاً منجر به افزایش دقت مدل در تشخیص انجمن‌ها خواهد گردید. روش ارائه‌شده این مقاله شامل دو بخش اساسی است. بخش اول معرفی یک روش تعبیه گراف برای شبکه‌های پیچیده پویاست که با حفظ ساختار شبکه آن را به فضایی با ابعاد کوچک‌تر تعبیه می‌کند که این روش تعبیه مبتنی بر یادگیر عمیق 5LSTM است [11]. بخش دوم ارائه مدلی است که از خوشه‌بندی جمعی6 برای تشخیص انجمن‌ها استفاده می‌کند. تحقیقات پیشین نشان دادند به‌کارگیری اجماعی از خوشه‌بندها نسبت به خوشه‌بندی تکی، عملکرد بسیار چشم‌گیرتری دارد [12] تا [15]. ورودی مدل تشخیص انجمن‌ها همان تعبیه گراف است و چالش‌های عمده در حوزه تعبیه گراف به شرح زیر هستند [16]:

-        درک ناقص از نمایش تعبیه آموخته‌شده: در طول دهه گذشته، چندین روش تعبیه گراف پیشنهاد گردیده است که هدف همه آنها حفظ ویژگی‌های متغیر می‌باشد. با این حال، درک تفاوت اصلی بین آنها و توصیه‌کردن روش‌های تعبیه برای یک گراف جدید هنوز چالش‌برانگیز است.

-        ساده‌سازی بیش از حد داده‌های دنیای واقعی: داده‌های دنیای واقعی غالباً چندوجهی بوده و حاوی اطلاعات بیشتری نسبت به داده‌های ثبت‌شده توسط گره‌ها و یال‌های گراف‌ها هستند. روش‌های اخیر نیز بر ثبت ویژگی‌های گره در تعبیه شبکه تمرکز دارند؛ اما ویژگی‌های یال که ممکن است تأثیر زیادی بر درک این شبکه داشته باشند، خیلی مطالعه نشده‌اند.

-        فقدان مدل‌های تعبیه برای گراف‌های پویا: اکثر روش‌های جدید بر روی یک تصویر لحظه‌ای از یک گراف متمرکز هستند. شبکه‌های دنیای واقعی اغلب با پیشبرد زمان و پیوستن گره‌های جدید و یال‌های جدید در حال تکامل هستند و بنابراین ثبت پویایی غیربدیهی و چالش‌برانگیز است.

در روش تعبیه گراف این مقاله سعی خواهد شد که چالش‌های اساسی مذکور رفع و روشی ارائه گردد که پویایی شبکه را در نظر گرفته و تعبیه‌ها را برای گراف‌های جریانی به‌روزرسانی کند و بتواند الگوهای موقتی را در گراف‌های متوالی ثبت نماید.

در بخش مربوط به تشخیص انجمن‌ها روش خوشه‌بندی جمعی پیشنهادی به‌طور خلاصه به شرح زیر تشریح خواهد شد:

1)        یک چارچوب کلی برای انتخاب خوشه‌بندی جمعی پیشنهاد می‌شود. علاوه بر این، مسئله خوشه‌بندی جمعی را به مسئله تشخیص انجمن در شبکه تبدیل می‌کند و سپس از شاخص پیمانه برای حل بهینه آن استفاده می‌نماید.

2)        یک مدل جدید درجه دوم اعداد صحیح7 برای حداکثرسازی درجه پیمانه8 به‌عنوان تابع اجماع پیشنهاد می‌شود.

3)        یک طرح انباشته حریصانه9 جدید به‌عنوان یک استراتژی جستجوی بسیار سریع برای حل مدل به‌ویژه در مجموعه داده‌های مقیاس بزرگ پیشنهاد می‌شود.

4)        الگوریتم پیشنهادی را با یک مثال توصیفی و بحث در مورد پیچیدگی زمان و مکان و همچنین تحلیل همگرایی غنی می‌کنیم.

نوآوری اساسی روش پیشنهادی این مقاله، ترکیب دو مدل پیشنهادی تعبیه گراف پویا با یک روش خوشه‌بندی مبتنی بر اجماع است.

در ادامه و در بخش بعد، ابتدا تعاریف مربوط به روش پیشنهادی آورده شده و سپس مقدمه‌ای بر روش‌های تعبیه گراف ارائه خواهد شد. همچنین توضیحاتی راجع به یادگیر عمیق10 و خوشه‌بندی جمعی آمده و کارهای گذشته در این بخش مرور خواهند گردید. بخش 3 روش پیشنهادی را ارائه می‌دهد. در بخش 4 نتایج ارزیابی‌های انجام‌شده با مجموعه داده‌های واقعی آمده و بخش نهایی مقاله شامل نتیجه‌گیری است.

2-       ادبیات تحقیق و مرور منابع

در این بخش سعی گردیده که ابتدا تعاریف مرتبط با روش ارائه‌شده در این مقاله مختصراً بیان شوند و سپس روش‌های تعبیه گراف تشریح گردد. در ادامه، خوشه‌بندی جمعی نیز توضیح داده شده و نهایتاً سعی گردیده تا جدیدترین کارهای گذشته در این حوزه مرور شوند.

تعریف ۱: گراف

گراف img0 مجموعه‌ای از img0 رأس و img0 یال است. ماتریس مجاورت img0 از گراف img0 شامل وزن‌های نامنفی همراه با هر یال است؛ به‌طوری که اگر img0 و img0 به هم متصل باشند آنگاه img0 و اگر img0 و img0 به هم متصل نباشند آنگاه img0 است. به‌طور کلی وزن یال img0 به‌عنوان یک معیار شباهت بین گره‌های img0 و img0 محسوب می‌شود که هرچه وزن یال بیشتر باشد، انتظار می‌رود که دو گره شباهت بیشتری داشته باشند.

تعریف ۲: مجاورت مرتبه اول

مجاورت مرتبه اول نشان می‌دهد که آیا بین جفت‌رئوس یالی وجود دارد یا خیر. دو رأس را مجاور می‌گوییم، اگر یک یال بین آنها وجود داشته باشد. در اینجا مجاورت رئوس با یال متصل‌کننده آنها تعریف می‌شود. وزن‌های یال img0 مجاورت مرتبه اول بین گره‌های img0 و img0 نامیده می‌شوند؛ چون اولین معیار شباهت بین دو گره هستند.

تعریف ۳: مجاورت مرتبه دوم

مجاورت مرتبه دوم بین یک جفت از گره‌ها، مجاورت ساختار همسایگی آنها را توصیف می‌کند. فرض کنید که img0 نشان‌دهنده مجاورت مرتبه اول بین img0 و سایر گره‌ها باشد. سپس مجاورت مرتبه دوم بین img0 و img0 با شباهت img0 و img0 تعیین می‌شود. مجاورت مرتبه دوم همسایگی این دو گره را با هم مقایسه می‌کند و اگر همسایه مشابهی داشته باشند، آنها را به‌عنوان همسایه لحاظ می‌نماید. تعریف مجاورت‌های درجه بالاتر با استفاده از معیارهای دیگر مثل شاخص کاتز11، رتبه صفحه12، همسایه‌های مشترک و ... امکان‌پذیر است.

تعریف ۴: تعبیه گراف

با توجه به گراف img0، تعبیه گراف یک نگاشت img0 است به‌گونه‌ای که img0 باشد و تابع img0 برخی معیارهای مجاورت تعریف‌شده در گراف img0 را حفظ کند. بنابراین تعبیه نگاشت هر گره به یک بردار ویژگی با ابعاد کم و تلاش برای حفظ نقاط اتصال بین رأس‌ها است. مثلاً یک تعبیه حفظ‌کننده مجاورت  مرتبه  اول  ممکن  است  با  به‌حداقل‌رساندن img0 

به‌دست آید. فرض کنید که دو جفت گره img0 و img0 با نقاط اتصال مرتبط باشند؛ به‌گونه‌ای که img0 است. در این حالت، دو جفت گره img0 به نقاط در فضای تعبیه نگاشت خواهند شد که از نگاشت img0 به یکدیگر نزدیک‌تر هستند. تعبیه گراف پویا، مفهوم تعبیه را به گراف‌های پویا تعمیم می‌دهد.

تعریف 5: تشخیص انجمن

مفهوم تشخیص انجمن در علم شبکه به‌عنوان روشی برای یافتن گروه‌ها در سیستم‌های پیچیده از طریق نمایش در یک گراف پدیدار شده است. روش‌های تشخیص انجمن، زیرشبکه‌هایی را پیدا می‌کنند که از نظر آماری، پیوندهای قابل‌ توجهی بین گره‌های یک گروه نسبت به گره‌ها در گروه‌های مختلف دارند [16].

تعریف 6: یادگیر عمیق

مدل‌های یادگیر عمیق، مدل‌های برگرفته از یادگیر ماشین در هوش مصنوعی هستند که به‌طور خودکار ویژگی‌های مربوط را از یک گراف استخراج می‌کنند.

2-1 تعبیه گراف

بسیاری از وظایف مهم در تجزیه و تحلیل شبکه، شامل پیش‌بینی بر روی گره‌ها و یا لبه‌های یک گراف است که به الگوریتم‌های مؤثر برای استخراج الگوهای معنادار و ساخت ویژگی‌های پیش‌بینی نیاز دارد. اخیراً در میان بسیاری از تلاش‌ها برای رسیدن به این هدف، تعبیه گراف یعنی یادگیری نمایش با ابعاد کم برای هر گره در گراف که ارتباط آن را با گره‌های دیگر به‌طور دقیق نشان می‌دهد، توجه زیادی را به خود جلب کرده است. نشان داده شده که تعبیه گراف در بسیاری از وظایف یادگیری نظارت‌شده مانند طبقه‌بندی گره13، پیش‌بینی لینک14 و ساخت گراف15 
و خوشه‌بندی16، نسبت به جایگزین‌ها برتری دارد [17] تا [20]. اکثر روش‌های موجود بر روی گراف‌های ایستا تمرکز دارند [21] تا [23]. از جمله روش‌های ایستا می‌توان به مدل‌های مبتنی بر تجزیه مقادیر منفرد (SVD) اشاره نمود که ماتریس مجاورت لاپلاسین یا مرتبه بالا را برای ایجاد تعبیه گره تجزیه می‌کنند [24]. سایر موارد شامل مدل‌های مبتنی بر قدم‌زدن تصادفی17 [25]، تعبیه‌هایی را از قدم‌زدن تصادفی محلی و بسیاری دیگر ایجاد می‌کنند. اخیراً در [26] مدلی ابتکاری به نام SDNE طراحی شده که از یک رمزگذار خودکار عمیق برای مدیریت غیرخطی‌بودن برای تولید تعبیه‌های دقیق‌تر استفاده می‌کند [26]. با این حال در کاربردهای عملی، بسیاری از گراف‌ها مانند شبکه‌های اجتماعی، پویا هستند و در طول زمان تکامل می‌یابند [27] و [28]. معمولاً ما گراف‌های پویا را به‌عنوان مجموعه‌ای از تصاویر لحظه‌ای گراف18 [28] و [29] در مراحل زمانی مختلف نشان می‌دهیم [30] و [31]. در ادامه برخی از مشهورترین روش‌های تعبیه گراف در جدول 1 بررسی شده است.

2-2 خوشه‌بندی جمعی

دو گرایش جدید در رویکردهای خوشه‌بندی جمعی وجود دارد: انتخاب خوشه‌بندی جمعی و بهینه‌سازی اجماع. در این بخش به بررسی برخی از مطالعات به‌روز در این زمینه‌ها پرداخته می‌شود.

2-2-1 انتخاب خوشه‌بندی جمعی

در اکثر مطالعات قبلی، همه پارتیشن‌ها و خوشه‌های آنها در اجماع، دارای وزن یکسانی در تصمیم‌گیری نهایی هستند [37] و [38]. با این حال از نظر منطقی به نظر می‌رسد سنجش ایده‌های بهتر، تصمیم‌گیری نهایی مجمع را تقویت می‌کند. در رویکرد انتخاب خوشه‌بندی جمعی، ایده این است که زیرمجموعه‌ای از خوشه‌بندی‌های پایه را انتخاب کنیم تا پارتیشن توافقی حاصل از این زیرمجموعه برابر یا بهتر از مجمع کامل باشد. انتخاب خوشه‌بندی جمعی از آموزش یادگیری گروه نظارت‌شده پیروی می‌کند [39]. مسئله انتخاب خوشه‌بندی جمعی برای اولین بار در [40] معرفی و بیشتر در [41] تا [46] بررسی شد. در روش پیشنهادی [47]، ابتدا مجموعه‌های خوشه‌ای چندگانه تولید می‌شوند و سپس مجمعی با تنوع میانه برای تولید خوشه‌بندی نهایی انتخاب می‌گردد. در مقابل، فرن و لین در [41] به دنبال انتخاب یک زیرمجموعه کوچک از یک مجموعه داده‌شده بزرگ برای تشکیل مجمع نهایی هستند. آنها روش‌های انتخاب مجمع خود را بر اساس کیفیت و تنوع (دو عامل تأثیرگذار در عملکرد خوشه‌بندی جمعی) طراحی کردند و از معیار اطلاعات متقابل نرمال (NMI) استفاده نمودند که ابتدا توسط استرل و گاش در [38] تعریف شد و در [37] تکامل یافت تا پارتیشن‌های اولیه را ارزیابی کنند. آنها با نتایج تجربی خود نشان دادند که انتخاب زیرمجموعه‌ای از پارتیشن‌ها، نتایج بهتری نسبت به پارتیشن‌های کامل به همراه دارد. مشابه فرن و لین [37]، علیزاده و همکاران در [44] اخیراً یک روش انتخاب پیشنهاد داده‌اند که مجموعه‌ای از خوشه‌های عملکرد بهتر را ایجاد می‌کند. آنها ایده انتخاب خوشه‌بندی جمعی را از سطح پارتیشن‌ها به خوشه‌های فردی گسترش دادند و معیار جدیدی به نام MAX را برای ارزیابی پایداری خوشه‌ها معرفی کردند و به‌طور تجربی نشان دادند که انتخاب خوشه‌های واجد شرایط بالا با توجه به معیار MAX، پارتیشن اجماع بهتری را به همراه دارد. این بدان معنی است که بین ثبات خوشه‌های انتخاب‌شده و عملکرد خوشه‌بندی نهایی قیاس وجود دارد. علیزاده و همکاران در [39] معیار اصلاح‌شده‌ای MAX را برای ارزیابی پایداری خوشه‌های فردی به نام معیار 19AAPMM معرفی کردند.

2-2-2 بهینه‌سازی اجماع

یکی از روندهای بسیار جدید در مسئله خوشه‌بندی جمعی، نگاشت مسئله به یک بهینه‌سازی ریاضی است. در این رویکرد، پارتیشن اجماع از حل یک روش بهینه‌سازی به‌دست می‌آید. با توجه به مجموعه‌ای از نتایج خوشه‌بندی، هدف مسئله بهینه‌سازی، یافتن پارتیشن بهینه از طریق حداکثرکردن (حداقل‌سازی) یک تابع هدف است. یک ویژگی مشترک در بیشتر مطالعات قبلی، تکیه بر مدل‌سازی نمونه‌ای از مسئله خوشه‌بندی جمعی به‌عنوان یک گراف شامل تعدادی گره و یال است. گره‌ها معمولاً نقاط داده را و یال‌ها مقداری از شباهت بین گره‌ها را نشان می‌دهند که 
از مجموعه داده‌‌شده محاسبه می‌گردند. نمایش گراف یک مجمع، صرف نظر از پیچیدگی الگوریتم برای کار، احتمالاً نتایجی کمتر از حد بهینه ایجاد می‌کند. تحقیقات جدیدتر در زمینه خوشه‌بندی جمعی تمایل به فرمول‌بندی مسئله به عنوان یک مسئله بهینه‌سازی و سپس حل آن 
با استفاده از حل‌کننده‌های ریاضی (یا حتی حل‌کننده‌های بهینه‌سازی هوشمند) را نشان می‌دهد [48] تا [52]. در [49] مدل بهینه‌سازی ارائه گردیده که توافق را به حداکثر می‌رساند و عدم توافق نتیجه، توافق را با 

 

[1] این مقاله در تاریخ 28 اردیبهشت ماه 1401 دریافت و در تاریخ 11 دی ماه 1401 بازنگری شد.

 

مجید محمدپور، دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران،
(email: m.mohammadpour@stu.yazd.ac.ir).

سیداکبر مصطفوی، دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران،
(email: a.mostafavi@yazd.ac.ir).

وحید رنجبر (نویسنده مسئول)، دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران،
(email: vranjbar@yazd.ac.ir).

[2] . Complex Network

[3] . Graph Embedding

[4] . Community Detection

[5] . Long Short-Term Memory

[6] . Ensemble Clustering

[7] . Integer Quadratic Model

[8] . Modularity

[9] . Greedy Agglomerative Scheme

[10] . Deep Learning

[11] . Katz

[12] . Page Rank

[13] . Node Classification

[14] . Link Prediction

[15] . Graph Generation

[16] . Clustering

[17] . Random Walk

[18] . Snapshots

[19] . Alizadeh-Parvin-Moshki-Minaei

جدول 1: برخی از مشهورترین روش‌های تعبیه گراف.

 

روش

توضیحات

مزایا و معایب

روش‌های مبتنی بر تجزیه 
مقادیر منفرد (SVD) [24]

الگوریتم‌های مبتنی بر تجزیه مقادیر منفرد، ارتباط بین گره‌ها را به شکل یک ماتریس نشان می‌دهند و این ماتریس را برای به‌دست‌آوردن تعبیه، تجزیه می‌کنند.

مزایا: استفاده گسترده در کاربردهای عملی، مقیاس‌پذیربودن، اجرای آسان

معایب: ایجاد نویز در راه حل، مثبت‌نبودن ماتریس مجاورت

تعبیه خطی محلی 1(LLE) [32]

روش LLE فرض می‌کند که هر گره، یک ترکیب خطی از همسایه‌های آن در فضای تعبیه است. این روش رابطه غیرخطی بین ویژگی‌ها را با تصویر‌کردن یک خم خطی محلی در فضای ویژگی می‌یابد.

مزایا: پیاده‌سازی ساده، استخراج ورودی‌های با اطلاعات بیشتر، یافتن وابستگی‌های غیرخطی ویژگی‌ها، حفظ ساختار همسایگی داده‌ها

معایب: عملکرد ضعیف در داده‌های مربوط به صوت

نگاشت ویژه لاپلاس [33]

هدف نگاشت ویژه لاپلاس، حفظ تعبیه دو گره با تأکید بر جفت فاصله‌های بزرگ است. نگاشت ویژه‌های لاپلاس از تابع جریمه درجه دو در فاصله بین تعبیه‌ها استفاده می‌کند.

مزایا: سادگی روش

معایب: عدم حفظ توپولوژی محلی در کاربردهای عملی

تعبیه کوشی2 [33]

بر فاصله کوتاه تأکید می‌کند و تضمین می‌نماید که هرچه دو گره شبیه‌تر باشند، در فضای تعبیه نزدیک‌تر خواهند بود.

مزایا: حفظ توپولوژی محلی در فضای تعبیه

معایب: پیچیدگی تابع هدف، عدم بهینگی در شبکه‌های پیچیده

تعبیه شبکه عمیق ساخت‌یافته 3(SDNE) [34]

از خودرمزگذارهای عمیق برای حفظ همسایگی‌های مرتبه اول و دوم شبکه استفاده می‌شود. این روش از توابع غیرخطی برای به‎دست‌آوردن قابلیت تعبیه استفاده می‌کند.

مزایا: حفظ ساختار شبکه محلی و سراسری، بهینگی برای شبکه‌های با ساختار پیچیده

معایب: از نظر محاسباتی هزینه‌بر و برای گراف‌های پراکنده بزرگ، غیربهینه

شبکه عصبی عمیق 4DNGR [35]

موج‌سواری تصادفی را با خودرمزگذار عمیق ترکیب می‌کند. این مدل شامل ۳ بخش است: 1) موج‌سواری تصادفی، 2) محاسبه اطلاعات متقابل نقطه‌به‌نقطه مثبت و 3) خودرمزگذارهای حذف نویز روی هم انباشته.

مزایا: استحکام مدل در حضور نویز در گراف، ثبت ساختار زیربنایی مورد نیاز برای وظایفی مانند پیش‌بینی لینک و طبقه‌بندی گره

معایب: هزینه‌ محاسباتی و غیربهینه برای گراف‎های پراکنده بزرگ

شبکه‌های کانولوشن گراف 
5(GCN) [36]

این مدل به‌طور تکراری، تعبیه‌های همسایه‌ها برای یک گره را تعریف می‌کند و از تابع به‌دست‌آمده و تعبیه آن در تکرار قبلی برای به‌دست‌آوردن تعبیه جدید استفاده می‌نماید و با تعریف یک عملگر کانولوشن بر روی گراف، با مشکل هزینه‌ محاسباتی و غیربهینه برای گراف‎های پراکنده بزرگ، مقابله می‌کند.

مزایا: حل مشکل عدم بهینگی برای گراف‌های پراکنده و بزرگ، مقیاس‌پذیری

معایب: وابستگی به فیلترهای مکانی و طیفی، یافتن مقدار مناسب برای عملگر استفاده‌شده در این روش

 

    1. Locally Linear Embedding                                           4. Deep Neural Networks for Graph Representations

    2. Cauchy Graph Embedding                                           5. Embedding Based Graph Convolutional Network

    3. Structural Deep Network Embedding

 

 

توجه به اعضای مجمع به‌طور همزمان به حداقل می‌رساند.

نویسندگان در [53] رابطه جدیدی از مسئله خوشه‌بندی جمعی را پیشنهاد کرده‌اند که از نمایش رشته برای رمزگذاری اطلاعات مجمع استفاده می‌کند. فرمول پیشنهادی از منطق فازی به‌منظور تعریف تابع هدف فازی استفاده می‌کند. آنها فرمول پیشنهادی خود را در یک مدل بهینه‌سازی ریاضی قرار دادند. اگرچه هر حل‌کننده ریاضی یا اکتشافی می‌تواند برای حل یک برنامه غیرخطی استفاده شود، آنها از یک الگوریتم ژنتیک تخصصی برای حل برنامه غیرخطی پیشنهادی خود استفاده کردند. نتایج تجربی آنها توانایی عملگرهای الگوریتم ژنتیک اصلاح‌شده را در مدیریت معضل اکتشاف- بهره‌برداری نشان داد. به موازات آن، تعدادی از مطالعات برای تبدیل یک وظیفه تشخیص انجمن به برنامه‌ریزی ریاضی در زمینه شبکه‌های پیچیده وجود دارد [54] تا [57]. محققان در این زمینه، مدل‌های ریاضی مختلفی را برای بهینه‌سازی برخی معیارهای کیفیت در انجمن‌ها تعریف کردند. از آنجایی که مجموعه خوشه اصلی 
و مسئله تشخیص انجمن، اصولاً به یکدیگر نزدیک هستند به نظر می‌رسد که پیوستن به آنها و استفاده از دستاوردهای یکی در دیگری پیشرفت‌های قابل توجهی را به همراه داشته باشد [58]. اخیراً در [58]
با موفقیت از خوشه‌بندی جمعی در تشخیص انجمن استفاده شده و نویسندگان نشان دادند که خوشه‌بندی جمعی را می‌توان با هر روش موجود به روشی خودسازگار ترکیب کرد و ثبات و دقت انجمن‌های حاصل را به‌طور قابل توجهی افزایش داد. علاوه بر این نویسندگان در [59]
اصل خوشه‌بندی جمعی را در گراف‌ها با ساخت مجموعه‌ای از گراف‌ها مشابه گراف اولیه، اعمال روش خوشه‌بندی برای هر یک از آنها، 
ساختن یک مجمع از پارتیشن‌ها و محاسبه اجماع، پیاده‌سازی کردند. پارتیشن‌بندی برای این نمایه به پارتیشن‌بندی گراف نهایی منجر می‌شود. آنها ادعا کردند که روش خوشه‌بندی bootstrap امکان بهبود کیفیت پارتیشن را به‌خصوص زمانی که عدم قطعیت در لبه‌های گراف وجود دارد، فراهم می‌کند. همچنین در [58] یک طرح اجماع برای تشخیص انجمن در شبکه‌های اجتماعی پیشنهاد گردید. نویسندگان در [58] نشان دادند 
که روش آنها جوامع پایدار و قوی را به همراه دارد. در این مقاله، چارچوبی برای ترسیم یک مسئله خوشه‌بندی جمعی به یک مسئله حداکثرسازی معیار پیمانه‌ای پیشنهاد می‌شود. سپس با استفاده از تجربیات قبلی 
در مدل‌سازی مسئله حداکثرسازی پیمانه‌ای به‌عنوان یک برنامه ریاضی، یک مدل ریاضی جدید، ارائه و بعداً با یک الگوریتم سریع حریصانه 
حل خواهد شد. ایده این مقاله بدین صورت تشریح می‌گردد: ابتدا یک روش تعبیه گراف برای شبکه‌های پیچیده پویا معرفی شده که این 
روش به‌عنوان گراف پیش‌پردازش به مدل اجماع پیشنهادی داده 
خواهد شد تا بتوان با عملکرد بالایی، انجمن‌ها در شبکه‌های پیچیده پویا تشخیص داده شوند.

 

G:\journal\Dr_Mostafavi_Paper_PSO\Complex Network\project\487524_1_En_10_Fig3_HTML.png 

شکل 1:  معماری تعبیه گراف پیشنهادی با روش یادگیر عمیق LSTM.

 

 

2-2-3 تابع توافقی

آخرین و نیز مهم‌ترین مرحله در چارچوب انتخاب خوشه‌بندی جمعی، تجمیع خوشه‌های انتخابی است. چند رویکرد اساسی برای ترکیب نتایج وجود دارد. یک رویکرد آن است که خوشه‌های انتخاب‌شده را به‌عنوان ورودی‌های الگوریتم هایپرگراف از جمله الگوریتم تقسیم‌بندی هایپرگراف (HGPA)، الگوریتم خوشه‌بندی (MCLA) و الگوریتم تقسیم‌بندی شباهت مبتنی بر خوشه (CSPA) در نظر بگیریم [60]. با توجه به خوشه‌های انتخاب‌شده به‌عنوان ورودی این الگوریتم‌ها، خروجی پارتیشن توافقی تولید می‌شود. روش دیگر برای استخراج پارتیشن نهایی این است که خوشه‌های انتخاب‌شده را به‌عنوان یک فضای داده جدید در نظر گرفته و از یک الگوریتم خوشه‌بندی مشترک مانند k-means یا k-means فازی برای پارتیشن‌بندی آنها استفاده کنیم [59]. خوشه‌بندی انباشت شواهد (EAC)، روش دیگری است که در آن اطلاعات هم‌رخدادی خوشه‌های انتخاب‌شده در ماتریس همبستگی انباشته می‌شوند. سپس یک الگوریتم پیوند برای استخراج پارتیشن اجماع از این ماتریس استفاده می‌گردد [39]، [44] و [45].

3-       روش پیشنهادی

در این بخش ابتدا روش تعبیه گراف که مبتنی بر روش یادگیر عمیق است مفصلاً تشریح می‌شود. از این مدل به‌عنوان یک مرحله پیش‌پردازش برای ورودی مدل پیشنهادی تشخیص انجمن‌ها که در ادامه آمده، استفاده شده است. در ادامه روش پیشنهادی مبتنی بر خوشه‌بندی جمعی برای تشخیص انجمن‌ها در شبکه‌های پیچیده پویا تشریح می‌گردد.

3-1 مسئله تعبیه گراف پویا

گراف وزن‌دار img0 را در نظر بگیرید که img0 و img0 به‌ترتیب مجموعه‌ای از رئوس و یال‌ها هستند. ماتریس مجاورت img0 را با img0 نشان می‌دهیم؛ یعنی برای یک یال img0، img0 وزن آن یال را در ماتریس مجاورت img0 نشان می‌دهد. در ماتریس مجاورت اگر یالی از img0 به img0 باشد، وزن آن یعنی img0 در ماتریس مجاورت img0 ثبت می‌گردد؛ در غیر این صورت اگر یالی وجود نداشته باشد آنگاه img0 است. تکامل گراف img0 به‌صورت img0 نشان داده می‌شود که در آن img0 وضعیت نمودار را در لحظه img0 نشان می‌دهد. مسئله تعبیه گراف به این شکل تعریف می‌شود: با درنظرگرفتن تکامل گراف img0، هدف نمایش هر گره img0 در فضای برداری با ابعاد پایین img0 است که در آن img0 تعبیه گره img0 در زمان img0 با یادگیری نگاشت‌های img0 و img0 است به‌گونه‌ای که img0 می‌تواند الگوهای زمانی مورد نیاز برای پیش‌بینی img0 را ثبت کند. به عبارت دیگر، تابع تعبیه در هر مرحله زمانی از اطلاعات، از تکامل گراف برای ثبت پویایی‌های شبکه استفاده می‌کند و در نتیجه می‌تواند انجمن‌ها را با دقت بالاتری تشخیص دهد.

3-1-1 مدل یادگیری

روش تعبیه گراف پیشنهادی، یک مدل یادگیر عمیق است که به‌عنوان ورودی، یک مجموعه از گراف‌های قبلی را می‌گیرد و به‌عنوان خروجی، گراف در گام زمانی بعدی را تولید می‌کند؛ بنابراین تعاملات غیرخطی بین رئوس در هر گام زمانی را به‌دست می‌آورد.

پیشرفت‌های اخیر در یادگیر عمیق نظارت‌نشده، نشان داده که رمزگذارهای خودکار1 می‌توانند با موفقیت بازنمایی‌های کم‌بعدی بسیار پیچیده به داده‌ها برای وظایف مختلف بیاموزند. مدل تعبیه گراف پویا از یک رمزگذار خودکار عمیق برای نگاشت داده‌های ورودی به یک فضای نهفته غیرخطی بالا استفاده می‌کند تا روندهای اتصال را در یک تصویر لحظه‌ای گراف در هر مرحله زمانی ثبت کند. مدل پیشنهادی برای تعبیه گراف پویا، یک مدل نیمه‌نظارت‌شده است و ترکیبی از دو تابع هدف مربوط به مجاورت مرتبه اول و مجاورت مرتبه دوم را به حداقل می‌رساند. مدل رمزگذار خودکار در شکل 1 نشان داده شده و نمادهای مورد استفاده در این مدل همانند روش [61] هستند.

چون تعبیه گراف، تکامل زمانی لینک‌ها را ثبت می‌کند، این امکان را می‌دهد تا لینک گراف را در گام زمانی بعدی پیش‌بینی کند [61]. این مدل، تعبیه شبکه در مرحله زمانی img0 را با بهینه‌سازی تابع زیان زیر یاد می‌گیرد

img0        (1)

در اینجا بازسازی نادرست یال‌ها در زمان img0 با استفاده از تعبیه در مرحله زمانی img0 جریمه می‌شود. به‌حداقل‌رساندن این تابع زیان، پارامترها را به‌گونه‌ای تنظیم می‌کند که بتواند روابط الگوهای تکاملی بین گره‌ها را ثبت کند تا یال‌ها را در گام زمانی آینده برای یک تعبیه مناسب در گراف پیچیده پویا پیش‌بینی کند. تعبیه در مرحله زمانی img0 تابعی از گراف در مراحل زمانی img0 است. از ماتریس وزن‌دهی img0 مطابق [62] برای وزن‌دادن و بازسازی یال‌های مشاهده‌شده، بالاتر از یال‌های مشاهده‌نشده استفاده می‌گردد.

در اینجا برای img0 مقدار img0 خواهد بود که img0 یک ابرپارامتر کنترل‌کننده وزن جریمه یال‌های مشاهده‌شده است. توجه داشته باشید که img0 یک ضرب عنصر به عنصر را نشان می‌دهد. یک راه ساده برای گسترش خودرمزگذارها که به‌طور سنتی برای تعبیه گراف‌های ایستا [61] به گراف‌های زمانی استفاده می‌شوند، این است که اطلاعات مربوط به گراف‌های قبلی را به‌عنوان ورودی به خودرمزگذار اضافه کنیم. این مدل از چندین لایه تمام متصل برای مدل‌سازی اتصال گره‌ها در طول زمان استفاده می‌کند. برای یک ‌گره img0 با مجموعه بردار همسایگی img0، نمایش پنهان اولین لایه به‌صورت زیر آموخته می‌شود [62]

img0        (2)

که در آن img0 تابع فعال‌سازی و img0 و img0، img0 و img0 به‌ترتیب ابعاد بازنمایی آموخته‌شده توسط لایه اول، تعداد گره‌های گراف و پارامتر بازگشت هستند. نمایش img0امین لایه به‌صورت رابطه زیر تعریف می‌شود [62]

img0        (3)

توجه داشته باشید که مدل ارائه‌شده در [62] دارای img0 پارامتر است. چون اغلب گراف‌های دنیای واقعی پراکنده‌اند، یادگیری پارامترها می‌تواند چالش‌برانگیز باشد. برای کاهش تعداد پارامترهای مدل و رسیدن به یک یادگیری زمانی مؤثرتر، مدل تعبیه گراف پویا پیشنهاد شده است. در این مدل از شبکه‌های حافظه کوتاه‌مدت (LSTM) برای یادگیری تعبیه استفاده می‌شود. LSTM نوعی از شبکه‌های عصبی تکرارشونده (RNN) و قادر به رسیدگی به مسئله‌های وابستگی بلندمدت است. در گراف‌های پویا، وابستگی‌های طولانی‌مدت وجود دارند که ممکن است با خودرمزگذارهای تمام‌متصل ثبت نشوند. بازنمایی حالت پنهان یک شبکه LSTM به‌صورت زیر تعریف می‌شود [62]

img0        (4)

که در آن img0 حالات سلول LSTM را نشان می‌دهد، img0 ماتریس وزنی است که رفتار دروازه‌های به‌روزرسانی، فراموشی و خروجی را کنترل می‌کند، img0 مقدار راه‌اندازی دروازه فراموشی است که وظیفه کنترل جریان اطلاعات از گام زمانی قبلی را دارد، img0 نشان‌دهنده مقدار راه‌اندازی دروازه به‌روزرسانی است که وظیفه کنترل جریان اطلاعات جدید را بر عهده دارد، img0 مقدار راه‌اندازی دروازه خروجی را نشان می‌دهد و مشخص می‌کند چه میزان از اطلاعات گام زمانی قبل به همراه اطلاعات گام زمانی فعلی به گام زمانی بعد منتقل شود، img0 تابع فعال‌سازی سیگموئید، img0 حالت کاندیدای تخمینی جدید و img0 نشان‌دهنده بایاس است. تابع img0 کمک می‌کند تا مقادیری که در طول شبکه در جریان هستند تعدیل2 شوند. img0 شبکه سلولی متصل در لایه اول وجود دارد که در آن حالات، سلول و نمایش پنهان در یک زنجیره از img0 به img0 شبکه‌های LSTM منتقل می‌شوند. سپس بازنمایی لایه img0ام به‌صورت زیر مشخص می‌شود

img0        (5)

مشکل عبور بردار همسایگی پراکنده img0 گره img0 به شبکه LSTM این است که پارامترهای مدل LSTM (مانند تعداد سلول‌های حافظه، تعداد واحدهای ورودی، واحدهای خروجی و ...) که باید آموخته شوند بسیار زیاد هستند. در عوض، شبکه LSTM ممکن است زمانی قادر به یادگیری بهتر نمایش باشد که بردار همسایگی پراکنده به یک نمایش با ابعاد پایین کاهش یابد. برای رسیدن به این هدف در [62] مدلی مناسب پیشنهاد شده که در آن به‌جای انتقال بردار همسایگی پراکنده از یک کدگذار تمام‌متصل استفاده می‌شود تا نمایش پنهان با ابعاد پایین را بتوان به‌صورت زیر به‌دست آورد [62]

img0        (6)

که در آن img0 لایه خروجی کدگذار تمام‌متصل را نشان می‌دهد و این نمایش سپس به شبکه‌های LSTM منتقل می‌شود [62]

img0        (7)

سپس بازنمایی پنهان تولیدشده توسط شبکه LSTM به یک کدگشای تمام‌متصل منتقل می‌شود. شکل 1 معماری تعبیه گراف را برای شبکه‌های پیچیده پویا نشان می‌دهد.

3-1-2 بهینه‌سازی

در تابع استفاده‌شده در [62] برای بهینه‌سازی پارامترهای تابع زیان تعریف‌شده در بالا از روش گرادیان با توجه به مقادیر کدگشا به‌صورت (8) استفاده شده است

img0        (8)

که در آن img0 یک ماتریس وزن برای مدل می‌باشد. برای این مدل، گرادیان‌ها بر اساس واحدهای عصبی تکثیر می‌شوند تا مشتقات برای همه لایه‌های قبلی به‌دست آورده شوند. بعد از به‌دست‌آوردن مشتقات، مدل با استفاده از نزول گرادیان تصادفی (SGD) با روش تخمین لحظه انطباقی بهینه‌سازی خواهد شد [62]. در این روش علاوه بر پیچیدگی محاسباتی بالا، سرعت بهینه‌نمودن پارامترها به کندی انجام خواهد شد. بنابراین در این بخش برای بهینه‌نمودن پارامترهای مدل LSTM عمیق از الگوریتم ژنتیک  استفاده  خواهد  شد.  الگوریتم  ژنتیک  در  عین  سادگی،  قادر  است  با 

img0 

شکل 2:  بردار دودویی img0بعدی شامل یک کروموزوم از جمعیت برای انتخاب یا عدم انتخاب پارامترهای مدل.

 

سرعت قابل توجهی، پارامترهای LSTM عمیق را بهینه نماید. مراحل الگوریتم ژنتیک برای بهینه‌نمودن پارامترهای مدل در ادامه آمده است. شکل 2 یک کروموزوم را نشان می‌دهد که بیت‌های 1 نشان‌دهنده شرکت پارامتر در مدل و بیت‌های 0 نشان‌دهنده عدم شرکت پارامتر در مدل است.

کدکردن کروموزوم: هر کروموزوم شامل مجموعه‌ای از پارامترهای مربوط به یک شبکه عصبی عمیق شامل تعداد دوره‌ها، تعداد نورون‌های هر لایه و وزن‌های لایه توجه است.

مقداردهی اولیه جمعیت: جمعیت اولیه کروموزوم‌ها به‌طور تصادفی در بازه [0,1] ایجاد می‌شود.

لایه توجه: وزن‌های لایه توجه در هر کروموزوم روی ورودی‌های مسئله اعمال می‌شوند.

ایجاد مدل: در این مرحله به‌ازای هر کدام از اعضای جمعیت با توجه به تعداد دوره‌ها و تعداد نورون‌های لایه پنهان، یک مدل ایجاد می‌شود و با استفاده از مجموعه آموزش و با روش پس‌انتشار خطا آموزش می‌بیند که مدل به‌کاررفته در معماری پیشنهادی شبکه LSTM عمیق با سه لایه است.

انتخاب: به‌منظور انتخاب والدین برای انجام عمل ترکیب از مکانیزم انتخاب بر اساس نخبگی استفاده می‌شود.

اعمال عملگر تقاطع و جهش: بعد از انتخاب کروموزوم‌های والد، عملگرهای تقاطع و جهش برای ایجاد جمعیت جدید اعمال می‌شود.

معیار توقف: معیار توقف در الگوریتم، رسیدن به تعداد معینی از تکرارها است. در صورت اتمام الگوریتم، سه تا از بهترین کروموزوم‌های خروجی در نظر گرفته می‌شوند.

3-2 خوشه‌بندی جمعی پیشنهادی

در این مرحله، گراف تعبیه‌شده از مرحله قبل به یک مدل اجماع مبتنی بر خرد جمعی داده می‌شود. خوشه‌بندی جمعی فرایندی است که در آن چندین خوشه‌بندی‌ پایه با هم ترکیب می‌شود.

روند اجرای الگوریتم بدین گونه است که ابتدا اولین الگوریتم پایه اجرا شده و نتیجه آن پس از ارزیابی پراکندگی (باید توجه داشت چون اولین الگوریتم است هیچ الگوریتمی جهت ارزیابی درجه استقلال در بخش الگوریتم‌های انتخاب‌شده وجود ندارد و نتیجه ارزیابی استقلال کاملاً مستقل خواهد بود) به بخش الگوریتم‌های انتخاب‌شده که ما آن را با عنوان جامعه خردمند می‌شناسیم اضافه می‌گردد. سپس نوبت الگوریتم بعدی است که پس از تولید نتیجه به ارزیابی درجه استقلال و میزان پراکندگی آن می‌پردازیم و در صورتی که نتایج ارزیابی‌ از میزان آستانه تعیین‌شده بیشتر باشد افراز تولیدشده به داخل جامعه خردمند اضافه خواهد شد. در این روش در صورت رد نتیجه به‌دست‌آمده در هر بخش، فرایند ارزیابی نتیجه الگوریتم متوقف شده و به سراغ الگوریتم پایه بعدی خواهیم رفت. در این تحقیق برخلاف روش‌های پیشین خوشه‌بندی ترکیبی، کل افراز به‌دست آمده از یک الگوریتم خوشه‌بندی پایه را در صورت داشتن شرایط لازم وارد مجمع می‌کنیم و این گونه اصالت جواب حفظ می‌شود. مهم‌ترین تفاوت این روش با روش‌های قبلی را می‌توان موارد زیر دانست:

-        اولین تفاوت این روش نحوه ارزیابی الگوریتم خوشه‌بندی است که در این روش پس از اجرای هر الگوریتم پایه، استقلال و پراکندگی آن نسبت به سایر الگوریتم‌های داخل مجمع محاسبه می‌شود و در صورت داشتن شرایط، وارد مجمع می‌شود.

-        دوم اینکه الگوریتم‌ها در اینجا به‌طور غیرمتمرکز عمل می‌کنند و الگوریتمی که بدون کیفیت، پراکندگی و استقلال باشد قادر به ورود در مجمع نیست؛ لذا خطاهای غیرهم‌جهت به‌وجودآمده در این روش حذف شده و آثار جواب‌های هم‌جهت در مجمع بر روی هم افزوده خواهند شد که این کاملاً منطبق بر اصول حاکم بر خرد جمعی است.

-        سوم اینکه چون بعد از رسیدن جمعیت مجمع به تعداد مورد نظر ما هیچ گزینش دیگری برای تولید جواب نهایی نیاز نیست، کیفیت نتایج نهایی حفظ می‌شود.

در مورد پراکندگی آرا باید گفت چون ما در خوشه‌بندی جمعی با داده‌ها و نتایج خوشه‌بندی اولیه سروکار داریم، از واژه پراکندگی نتایج اولیه استفاده می‌کنیم و بر اساس این فرض و تعریف سورویکی از تنوع آرا آن را به این شکل بازنویسی می‌نماییم: «هر الگوریتم خوشه‌بندی پایه باید جداگانه و بدون واسطه به داده‌های مسئله دسترسی داشته و آن را تحلیل و خوشه‌بندی کند؛ حتی اگر نتایج آن غلط باشد.» در اینجا نتایج غلط موجب کشف عدم تنوع و جلوگیری از تکرار یک جواب خاص خواهد شد. در این تحقیق برای محاسبه مقدار پراکندگی یک خوشه از معیار AAPMM [39] استفاده می‌شود؛ چون این معیار هم از لحاظ پیچیدگی زمانی سریع‌تر از NMI است و هم مشکل تقارن آن را ندارد. معیاری که این تحقیق جهت سنجش پراکندگی نتیجه افراز یک خوشه‌بندی پایه استفاده کرده است 3A نام دارد که میانگین وزن‌دار AAPMM می‌باشد که به شرح زیر است [39]

img0        (9)

که img0 تعداد اعضای خوشه img0، img0 تعداد اعضای کل خوشه‌ها و img0 تعداد افرازهای الگوریتم پایه می‌باشد. در این تحقیق مطابق [39] مقدار آستانه img0 برای سنجش میزان پراکندگی الگوریتم خوشه‌بندی استفاده می‌شود که همواره بین صفر و یک است. پراکندگی از (10) محاسبه خواهد شد

img0        (10)

بنابراین مطابق با تعاریف بالا یکی از شرایط ورود، نتیجه‌ یک خوشه‌بندی به مجمع (11) است که شرط پراکندگی نام دارد

img0        (11)

نویسندگان در [39] نشان داده‌اند که هرچه میزان پراکندگی در میان خوشه‌بندهای اولیه بیشتر باشد، نتایج تولیدشده نیز از دقت بیشتری برخوردار هستند.

در این روش، نتیجه‌های خروجی خوشه‌بندهای‌ پایه با استفاده‌کردن 
از یک تابع توافقی با هم ترکیب می‌شوند و به تولید نتیجه‌ای به مراتب بهتر از روش‌های خوشه‌بندی منفرد منجر می‌گردد. با توجه به یک مجموعه داده img0 که در آن img0، img0امین نقطه 
در یک فضای ویژگی img0بعدی می‌باشد، مجموعه‌ای از راه حل‌های خوشه‌بندی img0 که از img0 الگوریتم خوشه‌بندی ضعیف به‌دست می‌آیند، یک اجماع نامیده می‌شوند. هر راه حل img0، پارتیشنی از داده‌ها درون img0 خوشه و img0 خوشه‌های نشان‌دهنده خوشه img0 از پارتیشن img0ام است [12].

ایده اصلی زیربنای چارچوب پیشنهادی، استفاده از دو اصل جدید به‌منظور افزایش کارایی خوشه‌بندی جمعی است. اولین مورد، انتخاب بهترین زیرمجموعه از خوشه‌ها به‌جای استفاده از همه نتایج اولیه است. همان طور که در بخش قبل بیان گردید، نشان داده شده که استفاده 
از زیرمجموعه‌ای از خوشه‌های با کیفیت بالا نتایج بهتری نسبت به خوشه‌های کامل در اجماع دارد. در چارچوب ارائه‌شده، ابتدا یک ماتریس شباهت3 ایجاد می‌گردد. اطلاعات خوشه‌های انتخاب‌شده در یک ماتریس شباهت img0 انباشته شده و شباهت دو نقطه داده با تعداد دفعاتی که 
هر دو نمونه داده در یک خوشه گروه‌بندی می‌شوند اندازه‌گیری می‌گردد. از آنجا که این معیار، هم‌زمانی نمونه‌ها را محاسبه می‌کند به آن ماتریس هم‌همبستگی4 نیز می‌گویند. خوشه‌ها بر اساس یک تابع توافقی [39] با هم ترکیب خواهند شد. دوم استفاده از مفهوم پیمانه‌ای‌بودن در شبکه‌های پیچیده می‌باشد که توسط محققین در [63] معرفی شده است. به حداکثر رساندن پیمانه‌ای‌بودن از طریق شبکه در طیف وسیعی از مطالعات [63] تا [65] نشان داده شده که منجر به یافتن انجمن‌های با پیمانه بالا می‌شود. این واقعیت ما را برانگیخت تا مسئله انتخاب خوشه‌بندی جمعی را به مسئله حداکثرسازی پیمانه‌ای تبدیل کنیم تا از این معیار به‌خوبی استفاده نماییم. با درنظرگرفتن شکاف بین این مسائل، یک رابطه جدید برای به حداکثر رساندن معیار پیمانه‌ای، معرفی و سپس یک الگوریتم جستجوی حریصانه جدید برای بهینه‌سازی تابع هدف در زمان بسیار سریع ارائه می‌گردد. ابتدا مجموعه‌ای از img0 پارتیشن اولیه با استفاده از الگوریتم‌های خوشه‌بندی ضعیف ارائه شده است. به‌دلیل ساده‌بودن روش c-means فازی که نتایج اولیه متفاوتی را به‌همراه دارد، از الگوریتم c-means برای این کار استفاده کردیم. سپس کیفیت کل خوشه‌های فردی موجود در اجماع با استفاده از معیار Rank محاسبه می‌شود. در مرحله بعد، جفت (خوشه؛ کیفیت) داریم که کیفیت هر خوشه مقدار Rank آن است. ما به سادگی یک آستانه را بر روی ارزش کیفیت هر خوشه اعمال می‌کنیم و آنهایی را که بالاتر از آستانه هستند برای شرکت در مجمع تصمیم‌گیری نهایی برمی‌گزینیم.

3-2-1 معیار شباهت

در خوشه‌بندی جمعی، هر خوشه‌بندی پایه از تعداد معینی خوشه پایه تشکیل شده است. برای به‌دست‌آوردن اطلاعات خوشه پایه، یک راهکار معمول این است که برچسب‌های خوشه پایه را به سطح شیء (یا سطح قطعه5 [66]) با ساخت یک ماتریس همبستگی، نگاشت کرد. ماتریس همبستگی، چگونگی هم‌رخدادی دو شیء را که در یک خوشه مشابه در میان چندین خوشه‌بند پایه گروه‌بندی می‌شوند، منعکس می‌کند. نگاشت مستقیم از برچسب‌های خوشه پایه به ماتریس همبستگی شیء به‌طور ضمنی فرض می‌کند که خوشه‌های مختلف مستقل از یکدیگر هستند؛ اما نگاشت مستقیم، اطلاعات غنی پنهان در رابطه بین خوشه‌های مختلف را در نظر نمی‌گیرد. برای این منظور، ابتدا باید دو مشکل فرعی در اینجا حل شود: 1) چگونگی تعریف شباهت اولیه بین خوشه‌ها و 2) نحوه ترکیب اطلاعات برای ایجاد شباهت خوشه‌ای قوی‌تر. از آنجایی که یک خوشه مجموعه‌ای از اشیای داده است، رابطه اولیه بین خوشه‌ها را می‌توان با ضریب جاکارد [66] بررسی نمود که شباهت بین دو مجموعه را با درنظرگرفتن اندازه اشتراک و اندازه اجتماع آنها اندازه‌گیری می‌کند. به‌طور رسمی، ضریب جاکارد بین دو خوشه img0 و img0 به‌صورت (12) محاسبه می‌شود [66]

img0        (12)

در (12)، علامت img0، اشتراک دو خوشه و علامت img0، اجتماع دو خوشه را نشان می‌دهد. اگر یک گراف img0 را در نظر بگیریم، آنگاه img0 را مجموعه گره‌های گراف و img0 مجموعه یال‌های گراف را تشکیل می‌دهند. وزن یک یال مابین دو گره img0 و img0 img0، در معیار تشابه جاکارد از (13) محاسبه می‌شود

img0        (13)

با ساخت گراف تشابه اولیه، گام بعدی این است که اطلاعات چندمقیاسی6 در گراف گنجانده شود تا شباهت خوشه‌ای افزایش یابد. فرایند قدم‌زنی تصادفی، فرایندی پویاست که روی گراف انجام می‌شود. اکثر رویکردهای تعبیه‌سازی بر نمایش همسایگی محلی گره‌ها تمرکز می‌کنند و نمی‌توانند ساختار گراف سراسری را به تصویر بکشند؛ یعنی روابط را با گره‌های دور حفظ کنند. قدم‌زنی تصادفی، یکی از روش‌هایی است که توانسته بر این مشکل فایق آید. فرایند قدم‌زنی تصادفی در هر مرحله با احتمال معینی از یک گره به یکی از همسایگان خود منتقل می‌شود. در روش قدم‌زنی تصادفی باید ماتریس احتمال انتقال ساخته شود. ماتریس احتمال انتقال، احتمال قدم‌زنی تصادفی بین دو گره را مشخص می‌کند. در این مقاله، ماتریس احتمال انتقال img0 بر روی گراف به‌صورت (14) محاسبه می‌شود

img0        (14)

که در آن img0 احتمال انتقال یک قدم‌زنی تصادفی از گره img0 به گره img0 در یک مرحله است که متناسب با وزن یال بین آنهاست. بر اساس ماتریس احتمال انتقال تک‌مرحله‌ای می‌توان ماتریس احتمال انتقال چندمرحله‌ای img0 را برای قدم‌زنی‌های تصادفی روی گراف به‌دست آورد

img0        (15)

img0امین و img0امین مدخل در img0 با img0 (احتمال انتقال یک قدم‌زنی تصادفی از گره img0 و img0 در مرحله img0) نشان داده شده است. از آنجایی که طول گام‌های مختلف قدم‌زنی‌های تصادفی می‌توانند اطلاعات ساختار گراف را در مقیاس‌های مختلف منعکس کنند، برای ثبت اطلاعات چندمقیاسی در گراف img0 از مسیرهای قدم‌زنی تصادفی در مراحل مختلف برای اصلاح شباهت خوشه‌ای استفاده می‌شود. به‌طور رسمی برای قدم‌زنی تصادفی که از یک گره img0 شروع می‌شود، مسیر حرکت تصادفی آن از مرحله 1 تا مرحله img0 به‌صورت img0 نشان داده می‌شود. بدیهی است که مسیر قدم‌زنی تصادفی img0مرحله‌ای (یعنی img0) که از گره img0 شروع می‌شود و دارای طول گام img0 است، یک تاپل img0 با مقیاس چندگانه (یا اطلاعات ساختاری چندمرحله‌ای) در همسایگی img0 است. با مسیر قدم‌زنی تصادفی هر گره به‌دست‌آمده و درنظرگرفتن شباهت مسیرهای قدم‌زنی تصادفی آنها می‌توان یک معیار مشابهت برای هر دو گره به‌دست آورد. به‌طور خاص، ماتریس شباهت جدید بین همه خوشه‌های img0 موجود به‌صورت (16) نمایش داده می‌شود

img0        (16)

که img0 نشان‌دهنده شباهت جدید بین دو خوشه img0 و img0 است. پس 
از به‌دست‌آوردن ماتریس تشابه خوشه‌ای img0، ماتریس شباهت جدید از سطح خوشه به سطح شیء نگاشت می‌شود. برای به‌دست‌آوردن ماتریس تشابه خوشه‌ای img0، ماتریس شباهت از سطح خوشه به سطح شیء طبق (17) و (18) نگاشت می‌شود

img0        (17)

img0        (18)

که در آن img0 حاصل‌ضرب نقطه‌ای دو بردار img0 و img0 را در خروجی می‌دهد. از آنجایی که ورودی‌های ماتریس احتمال انتقال همیشه غیرمنفی هستند، به‌ازای هر دو خوشه img0 و img0 در همه خوشه‌های img0 موجود، img0 است.

3-2-2 ایجاد ماتریس همبستگی و تابع توافقی

در این مقاله از یکی از جدیدترین ایده‌های موجود برای تابع توافقی استفاده شده که در آن اطلاعات خوشه‌های انتخاب‌شده در یک ماتریس شباهت img0 تجمیع می‌شوند [43]. با الهام از مسئله مربوط در زمینه شبکه اجتماعی (برای تشخیص انجمن در شبکه‌های پیچیده) می‌توان این ماتریس شباهت را به‌عنوان یک شبکه وزن‌دار بیان کرد. با این دیدگاه 
که شبکه‌های پیچیده دنیای واقعی در حال تغییر هستند، الگوریتم‌های تشخیص انجمن شبکه را می‌توان برای حل مسئله تابع توافقی به کار گرفت. تابع توافقی پیشنهادی، فرایند تقسیم‌بندی را در سطح خوشه انجام می‌دهد که از ماتریس شباهت خوشه‌ای تقویت‌شده img0 بهره می‌برد و همه خوشه‌های مجمع را به چندین زیرمجموعه گروه‌بندی می‌کند. به هر زیرمجموعه از خوشه‌ها، متاخوشه گفته می‌شود. سپس هر شیء داده با رأی اکثریت به یکی از متاخوشه‌ها اختصاص داده می‌شود تا اجماع نهایی ساخته شود. به‌طور خاص با درنظرگرفتن خوشه‌ها در مجمع به‌عنوان گره‌های گراف و استفاده از ماتریس تشابه خوشه‌ای img0 برای تعریف وزن‌های یال بین آنها می‌توان یک گراف شباهت خوشه جدید ساخت؛ به این معنا که img0 که در آن img0 مجموعه گره‌ها و img0 مجموعه یال‌هاست. وزن یال در گراف img0 توسط ماتریس شباهت خوشه‌ای تقویت‌شده img0 تعیین می‌شود. با توجه به دو خوشه img0 و img0، وزن بین آنها به‌صورت (19) تعریف می‌گردد

img0        (19)

سپس الگوریتم برش نرمال‌شده7 می‌تواند برای تقسیم گراف جدید به تعداد معینی از متاخوشه‌ها استفاده شود؛ یعنی

img0        (20)

که در آن img0 متاخوشه و img0 تعداد متاخوشه است. توجه داشته باشید که یک متاخوشه از تعداد مشخصی خوشه تشکیل شده و با توجه به یک شیء img0 و یک متاخوشه img0، شیء img0 ممکن است که به‌صورت صفر یا چند خوشه در داخل img0 ظاهر شود. به‌طور مشخص، امتیاز رأی img0 متاخوشه img0 را می‌توان به‌عنوان نسبت خوشه‌های موجود در img0 که حاوی شیء img0 هستند تعریف کرد. به این معنا که

img0        (21)

که در آن img0 تعداد خوشه‌ها را در img0 نشان می‌دهد. سپس با رأی اکثریت، هر شیء به متاخوشه‌ای که در آن بیشتر ظاهر می‌شود (یعنی با بالاترین امتیاز رأی) اختصاص داده می‌شود؛ به این معنا که

img0        (22)

اگر یک شیء img0 همان بالاترین امتیاز رأی را از دو یا چند متاخوشه مختلف به‌دست آورد (که در عمل به‌ندرت اتفاق می‌افتد)، آنگاه شیء به‌طور تصادفی به یکی از متاخوشه‌های برنده اختصاص داده می‌شود. با اختصاص هر شیء به یک متاخوشه از طریق رأی اکثریت و درنظرگرفتن اشیا در همان متاخوشه به‌عنوان یک تابع توافقی، نتیجه نهایی خوشه‌بندی جمعی را می‌توان به‌دست آورد.

فرض کنید که ماتریس تشابه اندازه همان طور که در شکل 3- الف آمده، از تشابه جاکارد مشتق شده است. هر ورودی img0 در این ماتریس شباهت نشان‌دهنده یک یال متصل گره img0 و img0 در گراف مربوط است که در شکل 3- الف نشان داده شده است. از آنجایی که بدیهی است که هر نمونه داده با خودش در یک خوشه قرار دارد، بدون ازدست‌دادن کلیت مسئله، قطر اصلی ماتریس شباهت را می‌توان روی صفر تنظیم کرد؛ یعنی گره‌ها در گراف شباهت به خودشان حلقه ندارند. با توجه به یک ماتریس شباهت، ماتریس پیمانه‌ای به سادگی با کم‌کردن وزن مورد انتظار یال بین گره‌های img0 و img0 از وزن واقعی آن img0 محاسبه می‌شود و بنابراین یک مقدار مثبت در ماتریس پیمانه‌ای نشان می‌دهد که یال مربوط، وزنی بیش از حد انتظار دارد. شکل 3- ب ماتریس پیمانه‌ای را نشان می‌دهد. ماتریس پیمانه‌ای به‌عنوان ورودی به الگوریتم پیوند مجموع (مرحله 0) وارد می‌شود. در هر مرحله، حداکثر مقدار در ماتریس پیدا می‌شود و شاخص‌های سطر و ستون آن به‌عنوان خوشه‌ای تجمیع‌شده ادغام می‌شوند. اینجا ورودی img0 بزرگ‌ترین مقدار در مرحله 0 است (شکل 3- ج)؛ به آن معنا که خوشه‌های نمایه‌شده با 1 و 2 باید ادغام شوند. حال سؤال این است که با ادغام این دو خوشه، 

[1] . Autoencoders

[2] . Regulate

[3] . Similarity Matrix

[4] . Co-association Matrix

[5] . Fragment

[6] . Multi-Scale Information

[7] . Normalized Cut

                     img0

img0 

شکل 3:  مثالی برای نشان‌دادن مراحل روش پیشنهادی.

 

 

ماتریس چگونه باید به‌روز شود. به‌عنوان مثال، مقدار جدید img0 چگونه محاسبه می‌شود. دو ورودی img0 و img0 را به‌عنوان مقدار جدید img0 اضافه می‌کنیم و بنابراین طبق (23) داریم

img0        (23)

ورودی‌هایی که باید در این مرحله به‌روز شوند با رنگ خاکستری در مرحله 0 شکل 3- ج مشخص گردیده‌اند و همین رویه برای ماتریس به‌روز‌شده img0 تکرار می‌شود و بعد از چهار مرحله به پارتیشن دوخوشه‌ای می‌رسد.

پس از اینکه ماتریس همبستگی ساخته شد، در مرحله بعد از یک تابع توافقی برای استخراج خوشه‌های نهایی از این ماتریس استفاده می‌شود. ماتریس همبستگی، ماتریس شباهت img0 است که هم‌رخدادی جفت الگوها را در یک خوشه به‌عنوان رأی برای ارتباط آنها می‌گیرد. پس از آن، ماتریس همبستگی به ماتریس پیمانه‌ای تبدیل می‌شود تا بتوان روش‌های حداکثرسازی پیمانه‌ای را بر روی آن پیاده‌سازی کرد. با دانستن تعداد خوشه‌ها در اکثر وظایف خوشه‌بندی، یک برنامه عدد صحیح درجه دوم جدید را برای حل مسئله معرفی می‌کنیم. نهایتاً یک رویکرد حریصانه جدید برای حل مؤثر مدل و کشف خوشه‌های نهایی ارائه می‌شود.

3-2-3 به حداکثر رساندن معیار پیمانه‌ای

یادآور می‌شود که ماتریس همبستگی مشتق‌شده، یک ماتریس شباهت و هدف در این مرحله، استخراج خوشه‌های نهایی از آن است. با توجه به ماتریس شباهت نقاط داده می‌توان آن را به‌عنوان یک گراف یا شبکه وزن‌دار مشاهده کرد. این تغییر دیدگاه به ما امکان می‌دهد الگوریتم‌های تشخیص انجمن شبکه را به‌عنوان تابع توافقی در مسئله خوشه‌بندی جمعی استفاده کنیم. در زمینه تشخیص انجمن شبکه، تعدادی الگوریتم برای استخراج مؤثر انجمن‌ها (خوشه‌ها) از یک شبکه ورودی وجود دارد [66]. یکی از محبوب‌ترین الگوریتم‌ها، روش بهینه‌سازی مبتنی بر پیمانه است [64]. روش پیمانه‌ای‌بودن نیومن- گیروان [64] که ابتدا در 2004 معرفی گردید، ‌به‌سرعت به عنصر ضروری بسیاری از روش‌های تشخیص انجمن‌ها تبدیل شده است. پیمانه‌ای‌بودن تا حد زیادی مورد استفاده‌ترین و شناخته‌شده‌ترین تابع کیفیت به‌منظور ارزیابی خروجی الگوریتم‌های تشخیص انجمن‌هاست.

نماد استفاده‌شده برای تعریف پیمانه‌ای‌بودن به‌صورت زیر ارائه می‌شود: ماتریس img0 فرضیه صفر تعداد یال‌های مورد انتظار (وزن مورد انتظار) بین هر دو گره img0 و img0 را نگه می‌دارد که img0 است. درجه  یک  گره img0  با img0 و  مجموع  درجات  همه  گره‌ها  با img0 

نشان داده می‌شود. پیمانه‌ای‌بودن یک پارتیشن img0، وزن کل یال‌های داخل خوشه‌ها منهای فرضیه صفر آن یال‌ها می‌باشد. به‌منظور مقایسه پیمانه‌ای‌بودن گراف‌های با اندازه‌های مختلف، بهتر است که این اختلاف را با یک ضریب img0 نرمال نمود؛ بنابراین پیمانه‌ای‌بودن یک عدد در بازه img0 نرمال می‌شود. فرض کنید img0 بردار به طول img0 است که img0 شامل مقادیر صحیح img0، پارتیشنی است که img0 برچسب خوشه img0امین نقطه داده را در img0 نشان می‌دهد که img0 نشان‌دهنده تعداد خوشه‌ها می‌باشد. مثلاً img0 نشان‌دهنده این است که نمونه داده img0 متعلق به خوشه 3 است و در نتیجه، پیمانه‌ای‌بودن یک پارتیشن img0 را می‌توان به‌صورت (24) نوشت

img0        (24)

که در آن img0، دلتای کرونکر1 را نشان می‌دهد که اگر آرگومان‌های آن یکسان باشد، مقدار آن 1 و در غیر این صورت 0 است. img0 به آن معناست که پارتیشن img0، یال درون خوشه‌ای بیش از حد انتظار تصادفی نمی‌دهد. مقادیر بیشتر از 0 نشان‌دهنده انحراف از تصادفی‌بودن است. در عمل مقادیر بیشتر از حدود 3/0 به نظر می‌رسد که پارتیشن‌بندی قابل توجهی  را  نشان  می‌دهد.  برای  ساده‌سازی،  ماتریس img0 را  با  ورودی‌های 

img0 به‌عنوان  ماتریس  پیمانه img0 می‌گوییم؛  بنابراین 

معادله پیمانه‌ای به‌صورت (25) ساده می‌شود

img0        (25)

توجه به این نکته ضروری است که وقتی تعداد خوشه‌ها img0 ناشناخته است، می‌توان آن را با img0 جایگزین کرد. هدف مسئله در این مرحله، یافتن گروه‌های مجزا از گره‌ها است که مجموع ورودی‌های متناظر در ماتریس پیمانه‌ای img0 را به حداکثر برساند. رابطه پیمانه‌ای به‌سرعت تحقیقات علمی در زمینه تشخیص انجمن در شبکه‌های پیچیده را متحول کرد و آرایه‌ای از الگوریتم‌های اکتشافی را برای بهینه‌سازی پیمانه‌ای توسعه داد. از آنجایی که هیچ یک از الگوریتم‌های اکتشافی برای مسئله حداکثرسازی پیمانه‌ای نمی‌توانند تضمین کنند که پارتیشن بهینه را تولید می‌کند، رویکرد برنامه‌ریزی ریاضی یک مکتب فکری در حل دقیق مسئله پیدا کرده است. با این حال، اکثر این مطالعات یک فرمول برنامه‌ریزی خطی/ غیرخطی (ILP/INLP) ارائه می‌دهند که از نظر محاسباتی بسیار گران‌تر از آن است که توسط حل‌کننده‌های رایج ILP/INLP حل شود.

3-2-4 جستجوی حریصانه سریع

اگرچه الگوریتم‌های تکاملی مانند الگوریتم ژنتیک یا شبیه‌سازی تبرید می‌توانند برای حل مسئله بیشینه‌سازی استفاده شوند، اما کارایی آنها به کیفیت عملگرهای ابداع‌شده‌ای بستگی دارد که حل‌کننده را با مسئله تطبیق می‌دهند. این طرح‌ها معمولاً کندتر از سایر روش‌های اکتشافی هستند. از سوی دیگر، یکی از سریع‌ترین مکانیسم‌های بهینه‌سازی، رویکرد حریصانه است. اگرچه این رویکرد، تضمینی برای رسیدن به بهینه سراسری نیست، اما در عمل معمولاً نتایج بهینه یا تقریباً بهینه را به همراه دارد. علاوه بر این، آنها معمولاً روش‌های سریعی هستند و در واقع، مهم‌ترین ویژگی یک الگوریتم حریصانه کارایی زمانی آن است. در اینجا یک رویکرد حریصانه برای حل مسئله بهینه‌سازی پیشنهاد می‌شود. فرض کنید که img0 یک ماتریس img0 باینری است که اگر img0 باشد، نشان می‌دهد که گره img0 متعلق به خوشه img0 بوده و در غیر این صورت img0 است. ویژگی غیرهم‌پوشانی مسئله خوشه‌بندی بلافاصله محدودیت img0 را  ارضا  می‌کند.  به  بیان  ساده،  این  محدودیت 

به‌دلیل ویژگی باینری متغیرها در img0، هر گره را در یک خوشه مشاهده می‌نماید. در این رابطه گره img0 و img0 متعلق به img0امین خوشه‌اند، اگر و فقط اگر img0 باشد. به عبارت دیگر img0 هم‌رخدادی هر جفت گره را در یک خوشه بررسی می‌کند. با توجه به تعداد خوشه‌های img0، مدل به‌صورت (26) تعریف می‌شود

img0        (26)

رابطه (10) دو قید را برای همه img0 و img0ها تعریف می‌کند. از آنجایی که img0 و img0 است، پیچیدگی قیود در این مدل img0 می‌باشد. علاوه بر این، چون ماتریس متغیر img0 دارای ابعاد img0 است، پیچیدگی تعداد متغیرها img0 می‌باشد. از آنجایی که img0 به img0 بسیار نزدیک‌تر از img0 است و به‌طور دقیق‌تر می‌توان گفت کمی بیشتر از img0 است، بنابراین این مدل همچنین در پیچیدگی متغیرها از رقبای خود بهتر عمل می‌کند. اگرچه این برنامه درجه دوم 0-1 یک موضوع قابل توجه در مدل‌سازی مسئله است، اما حل مسئله حداکثرسازی پیمانه‌ای از نوع NP- سخت می‌باشد. به‌طور کلی، حل‌کننده‌های برنامه درجه دوم می‌توانند برای معیارهای کوچک مورد استفاده قرار گیرند و برای مسائل مقیاس بزرگ، به‌ویژه مواردی که img0 هستند، کاربردی نیستند. در مرحله بعد الگوریتم حریصانه سریعی ارائه می‌شود که قادر است فضاهای بسیار بزرگ را در مدت زمان بسیار کوتاهی جستجو کند. الگوریتم پیشنهادی روش پایین به بالاست که همانند روش‌های پیوند تجمعی2 کار می‌کند و با درنظرگرفتن هر نقطه داده به‌عنوان یک خوشه تکی شروع می‌شود. سپس دو خوشه را ادغام می‌کند که به نظر می‌رسد بهترین گزینه ادغام در این مرحله باشد و تا زمانی که دیگر خوشه‌های برای ترکیب وجود نداشته باشد، ادامه می‌یابد. این رویکرد به‌طور رسمی در شکل 4 بیان می‌شود.

طرح بهینه‌سازی تجمعی پیشنهادی پس از تعدادی تکرار محدود متوقف می‌شود. در مرحله اول، img0 گزینه برای ادغام وجود دارد و پس از ادغام، گزینه‌های img0 در مرحله دوم وجود دارد و در نتیجه، گزینه‌های img0 در آخرین مرحله img0 وجود دارد؛ بنابراین به‌طور کلی، img0 مرحله  وجود  دارد  که img0 گزینه  برای  انتخاب  وجود  دارد.  تکنیک 

خوشه‌بندی پیوند تجمعی، یک ماتریس پیمانه‌ای img0 را دریافت می‌کند که نیاز به محاسبه و ذخیره مدخل img0 ورودی‌ دارد. این فضا کاملاً قابل قبول و نیز از اکثر الگوریتم‌های خوشه‌بندی دیگر پایین‌تر است. زمان مورد نیاز برای پیوند تجمعی برابر با سایر الگوریتم‌های خوشه‌بندی سلسله‌مراتبی، یعنی img0 است و بنابراین پیوند تجمعی را می‌توان به‌عنوان یکی از سریع‌ترین الگوریتم‌های خوشه‌بندی طبقه‌بندی کرد. شکل 5 شمای کلی روش پیشنهادی را نمایش می‌دهد.

 

Algorithm 1: Greedy Algorithm

Input: img0

Output: final partition img0

1. img0

2. img0

3. Repeat

4. Find the maximum entry in img0 and set img0 and img0 to its row and

           column indices.

5. Merge the two clusters img0 and img0 as a new cluster img0.

6. Update the img0 (derive img0 from img0) as

           follows:

7. foreach img01 to img0

8. img0

9. end

10. img0

11. Until img0 (only img0 clusters remains)

12 Return the merged indices in img0 as the final clusters, img0.

 

شکل 4:  شبه‌کد رویکرد حریصانه پیشنهادی.

 

4-       آزمایش‌ها و نتایج تجربی

در این بخش، آزمایش‌های مختلفی بر روی روش پیشنهادی انجام گرفته و نتایج آن با سایر روش‌های رقیب مقایسه می‌گردد و همچنین مجموعه داده‌های مورد استفاده شرح داده شده است. تمامی آزمایش‌ها 
بر روی یک سیستم 64بیتی img0 با پردازنده img0، فرکانس ساعت پردازنده 30/3 گیگاهرتز و 64 گیگابایت حافظه انجام شده است. در این بخش برای انجام آزمایش‌های مختلف و بررسی عملکرد روش پیشنهادی، سناریوهای مختلفی در نظر گرفته شده است. در سناریوی اول، روش پیشنهادی برای پیش‌بینی لینک بر روی چندین مجموعه داده واقعی و مصنوعی، مورد آزمایش قرار گرفته است. در سناریوی دوم برای ارزیابی تأثیر اجماع در روش پیشنهادی از معیارهای مختلفی مثل معیار دقت، اطلاعات متقابل نرمال3 و رند تنظیم‌شده4 استفاده گردیده است. روش اجماع پیشنهادی با روش‌های رقیب در شرایط یکسان بر روی چندین مجموعه داده موجود در سایت یادگیر ماشین مقایسه شده و پارامترهای مختلف برای روش پیشنهادی در جدول 2 آمده‌اند.

4-1 سناریوی اول

در سناریوی اول، آزمایش‌هایی را بر روی دو مجموعه داده دنیای 
واقعی و یک مجموعه داده مصنوعی برای ارزیابی الگوریتم پیشنهادی خود انجام می‌دهیم. ما فرض می‌کنیم که مدل‌های پیشنهادی از همه گره‌ها آگاه هستند و هیچ گره جدیدی در مراحل زمانی بعدی معرفی نمی‌شود. در عوض، یال‌های بین گره‌های موجود با یک الگوی زمانی خاص تغییر می‌کند. خلاصه مجموعه داده‌های استفاده‌شده در جدول 3 آمده است.

در سناریوی اول، روش پیشنهادی با روش‌های رقیب که در [61] ارائه شده‌اند از نظر معیار میانگین دقت متوسط5 و با اندازه تعبیه 64 در شکل 6 مقایسه شده‌اند. این معیار مطابق (27) محاسبه گردیده است

 

جدول 2: پارامترهای روش پیشنهادی.

 

اندازه جمعیت در الگوریتم ژنتیک

100

نرخ تقاطع

8/0

نرخ جهش

2/0

تعداد لایه‌های شبکه عمیق

4

نرخ یادگیری شبکه عمیق

0/1

بهینه‌ساز شبکه عمیق

آدام

تابع فعال‌ساز

سیگموئید

 

جدول 3: مجموعه داده.

 

مجموعه داده

تعداد گره‌ها

تعداد یال‌ها

مراحل زمانی

SBM

1000

56016

10

Hep-th

150-14446

268-48274

136

AS

7716

268-48274

733

 

img0        (27)

که img0 کسری از پیش‌بینی‌های درست در پیش‌بینی‌های بالای img0 است. در معادله img0، img0 و img0 به‌ترتیب یال‌هایی هستند که در انجمن به درستی پیش‌بینی شده‌اند. img0 میانگین دقت را در تمام گره‌ها نشان می‌دهد و مقادیر img0 برای آزمایش پیش‌بینی‌های برتر ساخته‌شده توسط مدل استفاده می‌شود. مقادیر img0 مستحکم6 هستند و میانگین پیش‌بینی‌ها برای همه گره‌ها را شامل می‌شوند. مقادیر بالای img0 نشان می‌دهند که مدل می‌تواند پیش‌بینی‌های خوبی را برای اکثر گره‌ها انجام دهد.

در این بخش، ما نتیجه عملکرد مدل‌های مختلف را برای پیش‌بینی لینک در مجموعه داده‌های مختلف ارائه می‌کنیم. همچنین مدل را بر روی گراف‌ها از مرحله زمانی img0 تا img0 که img0 نگاه به عقب مدل است آموزش می‌دهیم و لینک‌های گراف را در مرحله زمانی img0 پیش‌بینی می‌کنیم. img0 یک فراپارامتر در مدل است. برای یک نمودار در حال تکامل با مراحل img0، پیش‌بینی بالا را از img0 تا img0 انجام می‌دهیم و میانگین img0 پیش‌بینی لینک را گزارش می‌کنیم.

4-2 سناریوی دوم

در سناریوی دوم از آزمایش‌ها، روش خوشه‌بندی جمعی پیشنهادی 
با سایر روش‌های رقیب از نظر معیارهای NMI، AR و Accuracy مقایسه می‌شود. در این سناریو از داده‌های استاندارد سایت یادگیری ماشین استفاده شده است. شکل‌های 7 تا 9 به‌ترتیب روش پیشنهادی 
را از نظر مقدار NMI، AR و Accuracy با سایر روش‌های رقیب مقایسه نموده‌اند.

 

[1] . Kronecker Delta

[2] . Agglomerative Linkage Methods

[3] . Normalized Mutual Information

[4] . Adjusted Rand

[5] . Mean Average Precision

[6] . Robust

img0 

شکل 5:  شمای کلی روش پیشنهادی.

 

img0 

شکل 6:  مقایسه روش پیشنهادی با سایر روش‌ها از نظر معیار میانگین دقت متوسط.

 

img0 

شکل 7:  مقایسه روش پیشنهادی با سایر روش‌های رقیب از نظر معیار NMI.

 

img0 

شکل 8:  مقایسه روش پیشنهادی با سایر روش‌های رقیب از نظر معیار AR.

 

img0 

شکل 9:  مقایسه روش پیشنهادی با سایر روش‌های رقیب از نظر معیار Accuracy.

 

 

خلاصه نتایج به‌دست‌آمده از به‌کارگیری الگوریتم‌های مختلف خوشه‌بندی از نظر معیارهای NMI، AR و Accuracy در نمودارهای ترسیم‌شده در شکل‌های 7 تا 9 آمده‌اند. نتایج به دو بخش عمده تقسیم می‌شوند: مجمع کامل و انتخاب. مجمع کامل، رویکرد خوشه‌بندی جمعی مشترک را نشان می‌دهد که در آن از تمام نتایج اولیه برای یافتن پارتیشن توافقی استفاده می‌شود. انتخاب مخفف، رویکرد انتخاب خوشه‌بندی جمعی است که در آن تنها زیرمجموعه‌ای از نتایج اولیه بر اساس معیار AAPMM انتخاب می‌شوند. هر یک از بخش‌های اصلی مجدداً به دو روش مختلف تقسیم می‌شوند: اولی استفاده از استراتژی شناخته‌شده EAC برای جمع‌آوری نتایج در یک ماتریس همبستگی و استفاده از یک الگوریتم پیوند برای استخراج خوشه‌های نهایی است. دومین طرح جدید پیشنهادی است که اطلاعات انباشته‌شده در ماتریس همبستگی را به یک ماتریس پیمانه‌ای، تبدیل و الگوریتم پیوند جمع پیشنهادی را اعمال می‌کند. همه معیارهای NMI، AR و Accuracy در شکل‌های 7 تا 9 تأیید می‌کنند که الگوریتم پیشنهادی ما با به‌دست‌آوردن حداکثر عملکرد در اکثر موارد آزمایش، بهترین روش عملکردی است. این شکل صراحتاً نشان می‌دهد که چارچوب انتخاب پیشنهادی، بسیار بهتر از استراتژی اجماع کامل عمل می‌کند. همچنین تأیید می‌نماید که الگوریتم پیشنهادی به‌طور قابل توجهی از روش‌های قبلی در هر دو مجمع کامل و استراتژی انتخاب بهتر عمل می‌کند. به‌طور کلی، نتایج تجربی نشان می‌دهند 
که الگوریتم پیشنهادی به‌عنوان تابع اجماع مبتنی بر پیمانه‌ای انتخاب خوشه‌بندی جمعی قطعاً بهترین گزینه برای خوشه‌بندی داده‌های ورودی است.

4-3 سناریوی سوم

در این سناریو، روش پیشنهادی بر روی سه مجموعه داده دنیای واقعی و در ابعاد 128 و 256 با سایر روش‌های دیگر مقایسه شده است. همان طور که در نمودارهای ترسیم‌شده در شکل‌های 10 و 11 مشاهده می‌شود با افزایش تعداد ابعاد، مقدار میانگین دقت برای همه روش‌ها کاهش می‌یابد. با افزایش تعداد ابعاد، پیچیدگی فضای مسئله بیشتر شده و در 

img0 

شکل 10:  مقایسه روش پیشنهادی با سایر روش‌ها از نظر میانگین دقت و تعداد 128 بعد.

 

img0 

شکل 11:  مقایسه روش پیشنهادی با سایر روش‌ها از نظر میانگین دقت و تعداد 256 بعد.

 

 

نتیجه دقت روش‌ها نیز کاهش می‌یابند. همان طور که مشاهده می‌شود روش پیشنهادی با افزایش تعداد ابعاد، نسبت به سایر روش‌ها عملکرد بسیار بهتری را از خود نشان داده است.

5-       نتیجه‌گیری و پیشنهادهای آتی

در این مقاله، ابتدا روشی برای تعبیه گراف آمده است و این تعبیه به‌عنوان ورودی به مدل خوشه‌بندی جمعی تحویل داده گردید. نشان داده شد که با کاهش ابعاد فضای مسئله می‌توان به نتایج با دقت بالاتری در تحلیل شبکه‌های پیچیده پویا رسید. در این مقاله، یک چارچوب انتخاب خوشه‌بندی جمعی پیشنهاد گردید که وظیفه بهینه‌سازی در تابع اجماع 
را دارد. چارچوب پیشنهادی به هر دو روند انتخاب و بهینه‌سازی کمک می‌نماید تا عملکرد مسئله خوشه‌بندی جمعی را افزایش دهد. ما همچنین مسئله انتخاب خوشه‌بندی جمعی را به یک مدل برنامه‌نویسی ریاضی تبدیل کردیم و یک الگوریتم سریع حریصانه را برای حل آن پیشنهاد نمودیم. نتایج تجربی با اجراهای منفرد مجمع کامل شناخته‌شده روش EAC و همچنین روش انتخاب EEAC مقایسه گردید. مطالعه تجربی نشان داد که چارچوب انتخاب خوشه‌بندی جمعی مبتنی بر بهینه‌سازی پیشنهادی به‌طور قابل توجهی بهتر از سایر روش‌های مجمع کامل یا انتخاب، عمل می‌کند. از آنجایی که چارچوب انتخاب خوشه‌بندی جمعی ما تنها بهترین خوشه‌ها را برای تشکیل مجموعه نهایی انتخاب می‌کند، انتظار می‌رود که استفاده از تکنیک ما در روش‌های خوشه‌بندی قوی‌تر از k-means بتواند حتی به پارتیشن‌های بهتر مجموعه داده‌های پیچیده منجر شود. ما مسئله خوشه‌بندی جمعی را به یک برنامه ریاضی تغییر دادیم و یک مدل درجه دوم 0-1 را برای به حداکثر رساندن پیمانه‌ای به‌عنوان تابع اجماع پیشنهاد کردیم. اگرچه که الگوریتم ارائه‌شده در بهینه‌سازی پیمانه‌ای‌بودن به خوبی عمل می‌کند، اما خروجی را تضمین نمی‌کند که راه‌حل بهینه باشد. علاوه بر این، یافتن نتیجه بهینه برای هر مدل IP یک مسئله NP-complete است. بنابراین در آینده برای حل این مسئله، برخی از پیشرفت‌ها را در مدل‌سازی کار بهینه‌سازی ابداع خواهیم کرد. به بیان دقیق‌تر، پیشنهاد مدل‌سازی ریاضی دیگری که می‌تواند در یک زمان معقول به یک راه حل دقیق برای مجموعه‌های داده در مقیاس بزرگ ارائه شود، مسئله باز ما است که قصد داریم در کار آینده خود آن را بررسی کنیم. پیشنهاد دیگر برای آینده این است که مدل و الگوریتم حل ما را برای تابع اجماع مورد بازنگری قرار دهیم تا به‌طور خودکار تعداد مناسب خوشه‌هایی را که مجموعه داده‌های آن ناشناخته است، تعیین کنیم.

مراجع

[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.

 

مجید محمدپور تحصيلات خود را در مقاطع كارشناسي و كارشناسي ارشد مهندسی کامپیوتر به­ترتيب در سال‌هاي 1386 و 1393 در دانشگاه بعثت کرمان و دانشگاه علوم تحقیقات تهران به پايان رسانده است و در حال حاضر دانشجوی دکتری مهندسي كامپيوتر در دانشگاه یزد مي‎باشد. نام­برده هم­اکنون در چندین واحد دانشگاهی در رشته کامپیوتر مشغول به تدریس می‌باشد. از جمله زمینه‌های تحقیقاتی مورد علاقه ایشان عبارتند از: بهینه‌سازی تکاملی پویا، یادگیری عمیق، یادگیری فدرال، و اینترنت اشیا.

 

سید اکبر مصطفوی تحصيلات خود را در مقطع كارشناسي رشته مهندسی فناوری اطلاعات در سال 1387 در دانشگاه صنعتی شریف و مقاطع كارشناسي ارشد و دکتری شبکه­های کامپیوتری را به­ترتيب در سال­هاي 1389 و 1394 در دانشگاه صنعتی امیر کبیر به پايان رسانده است و هم­اكنون دانشیار دانشكده مهندسي كامپيوتر دانشگاه یزد مي‎باشد. زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: اينترنت اشيا، رايانش مه و ابري، امنيت شبكه، شبكه‌هاي بي­سيم و سيار.

 

وحید رنجبر بافقی تحصیلات کارشناسی خود را در دانشگاه صنعتی شیراز در رشته مهندسی فناوری اطلاعات در سال 1390 گذراند و مقطع کارشناسی ارشد فناوری اطلاعات خود را در دانشگاه صنعتی شریف در سال 1392 به پایان رساند، سپس در سال 1397 دکتری فناوری اطلاعات خود را از دانشگاه تهران دریافت کرد. وی هم­اکنون استادیار دانشکده مهندسی کامپیوتر دانشگاه یزد است و زمینه های تحقیقاتی مورد علاقه ایشان امنیت اطلاعات و شبکه، تحلیل شبکه های اطلاعاتی و اینترنت اشیا است.

 

 

 

 


رایمگ

يقوم نظام رایمگ بتنفيذ جميع عمليات الاستلام والتقييم والحكم والتحرير وتخطيط الصفحة والنشر الإلكتروني للمجلات العلمية.

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية

حقوق هذا الموقع الإلكتروني مملوكة لنظام Rimag Press Management. © 1438-1446

الصفحة الرئيسية| دخول| عنا| اتصل بنا|
[English] [فارسی] [en] [fa]