تعداد نشریات | 39 |
تعداد شمارهها | 1,170 |
تعداد مقالات | 8,437 |
تعداد مشاهده مقاله | 6,318,104 |
تعداد دریافت فایل اصل مقاله | 3,563,142 |
یک راهحل افزایشی جهت خوشهبندی محتوایی- ساختاری یک گراف | ||
علوم و فناوریهای پدافند نوین | ||
مقاله 10، دوره 11، شماره 1 - شماره پیاپی 39، خرداد 1399، صفحه 107-121 اصل مقاله (1.46 M) | ||
نوع مقاله: مقاله پژوهشی | ||
نویسندگان | ||
سامان کشوری* 1؛ محمدعلی جوادزاده2؛ حسن نادری3 | ||
1دانشگاه جامع امام حسین (ع) | ||
2استادیار دانشگاه جامع امام حسین (ع) | ||
3دانشگاه علم و صنعت ایران | ||
تاریخ دریافت: 21 فروردین 1398، تاریخ بازنگری: 05 مرداد 1398، تاریخ پذیرش: 13 خرداد 1399 | ||
چکیده | ||
خوشهبندی گرههای گراف از جنبه ساختاری یا محتوایی، همواره موردتوجه پژوهشگران حوزه دادهکاوی بوده است؛ اما به خوشهبندی گراف بر مبنای ساختار و محتوا بهطور ترکیبی کمتر توجه شده است. با توجه به نیاز خوشهبندی ساختاری-محتوایی در شبکههای اطلاعاتی که شبکههای اجتماعی نمونهای از آنهاست، در این مقاله الگوریتم خوشهبندی ICS-Cluster ارائهشده که هر دو جنبه ساختار و محتوا را بهصورت همزمان در نظر میگیرد. هدف این روش، رسیدن به خوشههایی با ساختار درونی منسجم (ساختاری) و مقادیر ویژگی (محتوایی) همگن در گراف است. در این روش ابتدا گراف اولیه به یک گراف ساختاری-محتوایی تبدیل میشود که در آن وزن هر یال (ارتباط) بیانگر شباهت ساختاری-محتوایی دو گره (موجودیت) است. خوشهبندی با توجه به وزن یالها بهصورت افزایشی انجام میشود بدین معنا که گرههای یالِ با وزن بالا بهعنوان خوشه در نظر گرفته میشوند و وزن یالهای متصل به خوشه با یکدیگر ادغامشده و بهصورت یک یال متصل به خوشه در نظر گرفته میشوند، این مراحل تا زمانی که الگوریتم به تعداد خوشه موردنظر کاربر برسد، ادامه خواهد یافت. الگوریتم ICS-Cluster به هر تعداد خوشه که مدنظر کاربر است، گراف را خوشهبندی میکند. مقایسه الگوریتم مطرحشده با سه الگوریتم خوشهبندی ساختاری- محتوایی ارائهشده، بر اساس معیارهای ششگانه سنجش کیفیت خوشه، بیانگر عملکرد مناسب روش ICS-Cluster است. این معیارها معیارهای ساختاریِ تراکم خوشه، خطای یال و پیمانگی، معیار محتواییِ میانگین شباهت، معیار ساختاری-محتوایی CS-Measure و زمان اجرای روشها است. | ||
کلیدواژهها | ||
خوشهبندی گراف؛ خوشهبندی ساختاری- محتوایی؛ گراف خصوصیت؛ استخراج خوشه | ||
مراجع | ||
[1] Sambhoos, K.; Nagi, R.; Sudit, M.; Stotz, A. “Enhancements to High Level Data Fusion Using Graph Matching and State Space Search”; Inform. Fusion 2010, 11, 4, 351-364.## [2] Zhou, L.; Wang, Q.; Fujita, H. “One Versus One Multi-Class Classification Fusion Using Optimizing Decision Directed Acyclic Graph for Predicting Listing Status of Companies”; Inform. Fusion 2017, 36, 80-89.## [3] Gross, G. A.; Nagi, R. “Precedence Tree Guided Search for the Efficient Identification of Multiple Situations of Interest – AND/OR Graph Matching”; Inform. Fusion 2016, 27, 240-254.## [4] Guedes, G. P.; Ogasawara, E.; Bezerra, E.; Xexeo, G. “Discovering Top-Non-Redundant Clustering in Attributed Graphs”; Neurocomputing 2016, 210, 45-54.## [5] Schoch, D.; Valente, T. W.; Brandes, U. “Correlations Among Centrality Indices and a Class of Uniquely Ranked Graphs”; Soc. Networks 50, 46-54.## [6] Johnson, M.; Paulusma, D.; Leeuwen, E. J. V. “Algorithms for Diversity and Clustering in Social Networks Through Dot Product Graphs”; Soc. Networks 2015, 41, 48-55.## [7] Ertem, Z.; Veremyev, A.; Butenko, S. “Detecting Large Cohesive Subgroups with High Clustering Coefficients in Social Networks”; Soc. Networks 2016, 46, 1-10.## [8] Vörös, A.; Snijders, T. A. B. “Cluster Analysis of Multiplex Networks: Defining Composite Network Measures”; Soc. Networks 2017, 49, 93-112.## [9] Opsahl, T.; Panzarasa, P. “Clustering in Weighted Networks”; Soc. Networks 2009, 31, 155-163.## [10] Aggarwal, C.; Wang, H. “Managing and Mining Graph Data”; Springer US, 2010.## [11] Patkar, S. B.; Narayanan, H. “An Efficient Practical Heuristic for Good Ratio-Cut Partitioning”; 16th Int. Conf. VLSI Design 2003, 1-6.## [12] Feldmann, A. E.; Foschini, L. “Balanced Partitions of Trees and Applications”; Algorithmica 2015, 71, 354-376.## [13] Newman, M. “Community Detection in Networks: Modularity Optimization and Maximum Likelihood Are Equivalent”; Phys. Rev. 2016, 94, 1-8.## [14] Bhatia, V.; Rani, R. “A Parallel Fuzzy Clustering Algorithm for Large Graphs Using PREGEL”; Expert Syst. Appl. 2017, 78, 135-144.## [15] Fortunatoa, S.; Hricb, D. “Community Detection in Networks: A User Quide”; Phys. Rep. 2016, 659, 1-44.## [16] Khatoon, M.; Banu, A. “A Survey on Community Detection Methods In Social Networks”; IJEME. 2015, 1, 8-18.## [17] Elhadi, H.; Agam, G. “Structure and Attributes Community Detection: Comparative Analysis of Composite Ensemble and Selection Methods”; Proc. 7th Workshop on Social Network Mining and Analysis 2013, 1-7.## [18] Harenberg, S.; Bello, G.; Gjeltema, L.; Ranshous, S.; Harlalka, J.; Seay, R.; Padmanabhan, K.; Samatova, N. “Community Detection in Large-Scale Networks: A Survey and Empirical Evaluation”; Computation Stat. 2014, 6, 426-439.## [19] Bu, Z.; Gao, G.; Li, H. J.; Cao, J. “CAMAS: A Cluster-Aware Multiagent System for Attributed Graph Clustering”; Inform. Fusion 2017, 37, 10-21.## [20] Weber L. M.; Robinson M. D. “Comparison of Clustering Methods for High-Dimensional Single-Cell Flow and Mass Cytometry Data”; Cold Spring Harbor Labs Journals 2016, 047613.## [21] Shchukin, V.; Khristich, D.; Galinskaya, I. “Word Clustering Approach to Bilingual Document Alignment”; First Conf. Machine Translation 2016, 2, 953-994.## [22] Skabar, A. “Clustering Mixed-Attribute Data Using Random Walk”; Procedia Comput. Sci. 2017, 108, 988-997.## [23] Xu, Z.; Cheng, J.; Xiao, X.; Fujimaki, R.; Muraoka, Y. “Efficient Nonparametric and Asymptotic Bayesian Model Selection Methods for Attributed Graph Clustering”; Knowl. Inform. Syst. 2017, 53, 239-268.## [24] Gross, G.; Nagi, R.; Sambhoos, K. “A Fuzzy Graph Matching Approach in Intelligence Analysis and Maintenance of Continuous Situational Awareness”; Inform. Fusion 2014, 18, 43-61.## [25] Boobalan, M. P.; Lopez, D.; Gao, X. Z. “Graph Clustering Using K-Neighbourhood Attribute Structural Similarity”; Appl. Soft Comput. 2016, 47, 216-223.## [26] Zhou, H.; Li, J.; Li, J.; Zhang, F.; Cui, Y. “A Graph Clustering Method for Community Detection in Complex Networks”; Physica A 2017, 469, 551-562.## [27] Bai, L.; Cheng, X.; Liang, J.; Guo, Y. “Fast Graph Clustering with a New Description Model for Community Detection”; Inform. Sci. 2017, 388, 37-47.## [28] Ruan, Y.; Fuhry, D.; Parthasarathy, S. “Efficient Community Detection in Large Networks Using Content and Links”; Proc. 22nd Int. Conf. World Wide Web WWW '13). ACM, New York, NY, USA, 2013, 1089-1098.## [29] Zhou, Y.; Cheng, H.; Xu, Y. J. “Graph Clustering Based on Structural/Attribute Similarities”; Proc. VLDB Endowment 2009, 2, 718-729.## [30] Parimala, M.; Daphne, L. “Graph Clustering Based on Structural Attribute Neighborhood Similarity (SANS)”; IEEE Int. Conf. Elec. Comput. Commun. Technol. 2015, 1-5.## [31] Pool, S.; Bonchi, F.; Leeuwen, M. “Description-Driven Community Detection”; ACM Trans. Intel. Syst. Technol. 2014, 03, 201-210.## [32] Rahmati, K.; Naderi, H.; Keshvari, S. “Content-Structural Graph Clustering and a New Measure For Its Evaluation”; Adv. Defence Sci. Technol. 2018, 03, 201-210. (In Persian)## [33] Halloush, R. “Overhearing-Aware Modified Dijkstra's Algorithm for Multicasting over Multi-Hop Wireless Networks”; Int. J. Commun. Netw. Distrib. Syst. 2016, 16, 240-260.## [34] Pool, S.; Bonchi, F.; Leeuwen, M. “Description-Driven Community Detection”; ACM Trans. Intel. Syst. Technol. 2014, 5, 28.## [35] Wang, M.; Wang, Ch.; Xu, Y. J.; Zhang, J. “Community Detection in Social Networks: An In-Depth Benchmarking Study with a Procedure-Oriented Framework”; Proceedings of the VLDB Endowment 2015, 8, 998-1009.## [36] Yang, J.; Leskovec, J. “Defining and Evaluating Network Communities Based on Ground-Truth”; Knowl. Inf. Syst. 2015, 42, 181-213.## [37] Biswas, A.; Biswas, B. “Defining Quality Metrics for Graph Clustering Evaluation”; Expert Syst. Appl. 2017, 71, 1-17.## | ||
آمار تعداد مشاهده مقاله: 416 تعداد دریافت فایل اصل مقاله: 164 |