A New Meta-heuristic Algorithm based on Multi-criteria Decision Making to Solve Community Detection Problem

Document Type : Research Paper

Authors

1 Assistant Prof. of Industrial Engineering, Islamic Azad University, North Tehran Branch, Iran

2 Ph.D. Candidate of Industrial Engineering, Islamic Azad University, North Tehran Branch, Iran

3 Ph.D. Candidate of Industrial Engineering, Islamic Azad University North Tehran Branch, Iran

Abstract

Community detection is one of the most significant issues in the field of social networks. The main purpose of community detection is to partition the network in such a way that the relations between components of the network are dense. Because of the strong relations among network members in these partitions, you can consider them as a community. Many researchers have developed several algorithms to solve such a problem. Therefore, we present a genetic algorithm based on Topsis which is a multi-criteria decision making method (MCDM). The proposed algorithm uses Topsis to rank solutions based on modularity and modularity density which are two of the most well-known criteria in community detection problem. Thereafter, crossover and mutation operators are only applied on solutions ranked by Topsis. The performance of the proposed algorithm has been evaluated through comparing it against classical genetic algorithm and a greedy one. The results showed that the proposed algorithm outperforms the other two methods. Since the application of MCDM approach has not been reported in the related literature, this paper can be considered as a basis for future studies.

Keywords

Main Subjects

References

اصغری اسکویی، محمدرضا؛ قاسم‌زاده، محمد (1395). کاربرد قواعد کشفی و الگوریتم ژنتیک در ساخت مدل ARMA برای پیش‌بینی سری زمانی. فصلنامۀ مدیریت فناوری اطلاعات، 8(1)، 26-1.
البرزی، محمود؛ پورزرندی، محمدابراهیم؛ خان‌بابایی، محمد (1389). به‎کارگیری الگوریتم ژنتیک در بهینه‌سازی درختان تصمیم‌گیری برای اعتبارسنجی مشتریان بانک. فصلنامۀ مدیریت فناوری اطلاعات، 2(4)، 38- 23.
بهشتی‌نیا، محمدعلی؛ فرازمند، ناهید (1394). ارائة سیستم پشتیبانی تصمیم نوین به‎منظور موازنة هزینه ـ انتشار دی‎اکسیدکربن گسسته در پروژه‌های ساخت: کاربردی از الگوریتم ژنتیک الگوبرداری. فصلنامۀ مدیریت فناوری اطلاعات، 7(1)، 48- 23.
بهشتی‌نیا، محمدعلی؛ قهرمانی، مانی (1395). ارائة سیستم پشتیبانی تصمیم مبتنی بر الگوریتم ژنتیک (مطالعة موردی: زمان‌بندی در زنجیرة تأمین). فصلنامۀ مدیریت فناوری اطلاعات، 8(3)، 476- 455.
تقوی‌فرد، محمدتقی؛ سادات‌حسینی، فریبا؛ خان‌بابایی، محمد (1393). مدل رتبه‌بندی اعتباری هیبریدی با استفاده از الگوریتم‌های ژنتیک و سیستم‌های خبرة فازی (مطالعة موردی: موسسة مالی و اعتباری قوامین). فصلنامۀ مدیریت فناوری اطلاعات، 6(1)، 46-31.  
حقیقی، الهام؛ منتظر، غلامعلی (1394). شناسایی عوامل مؤثر بر اعتمادسازی در شبکه‌های اجتماعی برخط به‎کمک روش الکترة فازی. فصلنامۀ مدیریت فناوری اطلاعات، 7(4)، 740- 715.
رضایی‌نور، جلال؛ لسانی، رضوان؛ زکی‌زاده، عاطفه؛ صفامجید، غدیر. (1393). بررسی شبکه‌های اجتماعی همکاری نویسندگی در حوزۀ فناوری اطلاعات با استفاده از تکنیک‌های شبکه‌های اجتماعی. فصلنامۀ مدیریت فناوری اطلاعات، 6(2)، 250- 229.
فتحیان، محمد؛ حسینی، محمد (1393). بررسی تأثیر اجتماعات در تقویت رفتار خرید مشتریان. فصلنامۀ مدیریت فناوری اطلاعات، 6(3)، 454- 435.
کاباران‌زاده قدیم، محمدرضا؛ رفوگر آستانه، حسین (1388). طراحی یک سیستم پشتیبان تصمیم‎گیری (DSS) در مدیریت برای حل مسئلۀ تسطیح منابع در مدیریت پروژه با رویکرد الگوریتم ژنتیک (GA). فصلنامۀ مدیریت فناوری اطلاعات، 1(3)، 88- 69.
کی‌پور، اعظم؛ براری، مرتضی؛ شیرازی، حسین. (1393). ارائة روشی جدید برای پیشگویی پیوند بین رأس‌های موجود در شبکه‌های اجتماعی. فصلنامۀ مدیریت فناوری اطلاعات، 6(3)، 486- 475.
References
Agarwal, G., & Kempe, D. (2008). Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B, 66(3), 409-418.
Alborzi, M., Pourzarandi, M., & Khanbabaei, M. (2011). Using Genetic Algorithm in Optimizing Decision Trees for Credit Scoring of Banks Customers. Journal of Information Technology Management, 2(4), 23-38. (in Persian)
Al-Ghazzali, T. (2009). Meta heuristics: from design to implementation. Chichester: John Wiley and Sons Inc.
Asghari Oskoei, M., & Ghasemmzade, M. (2016). Application of Heuristic Rules and Genetic Algorithm in ARMA Model Estimation for Time Series Prediction. Journal of Information Technology Management, 8(1), 1-26.
(in Persian)
Beheshtinia, M. A., & Farazmand, N. (2015). A Novel Decision Support System for Discrete Cost-CO2 Emission Trade-off in Construction Projects: The Usage of Imitate Genetic Algorithm. Journal of Information Technology Management, 7 (1), 23-48. (in Persian)
Beheshtinia, M. A., & Ghahremani, M. (2016). A Decision Support System Based on Genetic Algorithm (Case Study: Scheduling in Supply Chain). Journal of Information Technology Management, 8(3), 455-476. (in Persian)
Blondel, V.D., Guillaume, J.L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, P10008.
Boettcher, S., & Percus, A.G. (2001). Optimization with extremal dynamics. Physical Review Letters, 86(1), 5211–5214.
Brandes, U., Delling, D. & Gaetler, M. (2008). On Modularity Clustering. Transactions on Knowledge and Data Engineering, 20(2), 172-188.
Chen, M., Kuzmin, K., Boleslaw, K., & Szymanski, F. (2014). Community Detection via Maximization of Modularity and Its Variants. IEEE Transactions on Computational Social Systems,1(1), 46-65.
Choudhury, D. & Paul, A. (2013). Community Detection in Social Networks: An Overview. International Journal of Research in Engineering and Technology, 2(2), 6-13.
Duch, J., & Arenas, A. (2005). Community detection in complex networks using extremal optimization. Physical Review E, 72(2), 027104.
Fathian, M. & Hosseini, M. (2014). Investigating the Impact of Virtual Communities on Furtherance of Customers’ Buying Behavior. Journal of Information Technology Management, 6(3), 435-454. (in Persian)
Fortunato, S. & Barthelemy, M. (2007). Resolution limit in community detection. PNAS, 104(1), 36-41.
Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 1–100.
Ghorbanian, A. & Shaqaqi, B. (2015). A Genetic Algorithm for Modularity Density Optimization in Community Detection. International Journal of Economy, Management and Social Sciences, 4(1), 117-122.
Girvan, M., & Newman, M. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 99(12), 7821–7826.
Griechisch, E. & Pluhar, A. (2011). Community Detection by using the Extended Modularity. Acta Cybernetica, 20(1), 69-85.
Guimera, R. & Amaral, L. (2005). Functional Cartography of Complex Metabolic Networks. Nature, 433(2), 895-900.
Guoqiang, C. & Xiaofang, G. (2010). A Genetic Algorithm Based on Modularity Density for Detecting Community Structure in Complex Networks. Computational Intelligence and Security, 20(4), 151-154.
Hafez, A., Ghali, N., Hassanien, A. & Fahmy, A. (2012). Genetic Algorithms for community detection in social networks. Intelligent Systems Design and Applications, 10(2), 460-465.
Haghighi, E., & Montazer, G., (2016). Identifying the Effective Factors in Making Trust in Online Social Networks on the perspective of Iranian experts Using Fuzzy ELECTRE. Journal of Information Technology Management, 7(4), 715-470. (in Persian)
Kabaranzadeh Ghadim, M.R., & Astaneh, H.R. (2009). Designing a Decision Support System (DSS) schema with Applying Genetic Algorithm for Survey of Resource Leveling Problem-(Vehicles). Journal of Information Technology Management, 2(3), 69-88 . (in Persian)
Keypour, A., Barari, M, & Shirazi, H. (2014). Presenting a New Method for Link Prediction in Social Networks. Journal of Information Technology Management, 6(3), 475-486. (in Persian)
Leskovec, J., Lang, K. & Mahoney, M. (2010). Empirical comparison of algorithms for network community detection. ACM, 20(16), 631-640.
Li, Z., Zhang, S., Wang, R., Zhang, X., & Chen, L. (2008). Quantitative function for community detection, Physical Review E, 77(3), 157-178.
Massen, C.P., & Doye, J., (2005). Identifying communities within energy landscapes, Physical Review E, 71(4), 0461011-04610112.
Newman, M. (2006). Finding community structure in networks using the eigenvectors of matrices. Physical Review,1(3), 12-34.
Newman, M., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review,69(2), 22-38.
Pan, G., Zhang, W., Wu, Z., & Li., S. (2014). Online Community Detection for Large Complex Networks. PLoS ONE, 9(7), 168-188.
Pizzuti, C. (2008). GA-Net: A Genetic Algorithm for Community Detection in Social Networks. Computer Science, 5199(1), 1081-1090.
Rezaeenour, J., Lesani, R., Zakizadeh, A., & Safamajid, G. (2014). Evaluating Authorship Collaboration Networks in the Field of Information Technology Using Social Netwowk Techniques. Journal of Information Technology Management, 6(2), 229-250. (in Persian)
Shang, R., Bai, J., Jiao, L., & Jin, C., (2013) Community detection based on modularity and an improved genetic algorithm, Physica A: Statistical Mechanics and its Applications, 392(5), 1215-1231.
Shaqaqi, B., & Teymorpour, B., (2015). A new heuristic algorithm for modularity optimization in complex networks community detection. 11th International Industrial Engineering Conference, 7-8 January.
Shi, C., Yan, Z., Wang, Y., Cai, Y. & Wu, B. (2010). A Genetic Algorithm for Detecting Communities in Largescale Complex Networks. Advance in Complex System, 13(1), 3-17.
Taghavifard, M., Hosseini, F., & Khanbabaei, M. (2014). Hybrid credit scoring model using genetic algorithms and fuzzy expert systems Case study: Ghavvamin financial and credit institution. Journal of Information Technology Management, 6(1), 31-46. (in Persian)
Yue, Z., (2012). Extension of TOPSIS to determine weight of decision maker for group decision making problems with uncertain information. Expert Systems with Applications, 39(7), 6343-6350.
Zhang, H., Qiut, B., Giles, L., Foley, H. & Yen, J. (2007). An LDA-based Community Structure Discovery.Intelligence and Security Informatics, 400(2), 200-207.
 
Journal of Information Technology Management
Volume 10, Issue 2
2018
Pages 283-308

Files

Share

How to cite

Statistics