ارائه‌ روشی مبتنی بر رتبه‌بندی و الگوریتم انتشار گرما برای استخراج جامعه در شبکه‌های اجتماعی

الموضوعات : مجله فناوری اطلاعات در طراحی مهندسی

ملیحه ابراهیمی نژاد ¹ , سمانه حسن زاده ² , مهرداد جلالی ³

1 - دپارتمان مهندسی کامپیوتر، دانشکده 17 شهریور کرج، دانشگاه فنی و حرفه ای استان البرز، ایران
2 - 2دپارتمان مهندسی کامپیوتر فناوری اطلاعات، موسسه آموزش عالی اقبال لاهوری، مشهد،ایران
3 - گروه کامپیوتر دانشگاه آزاد اسلامی مشهد

تاريخ الإرسال : 17 الإثنين , رمضان, 1435 تاريخ التأكيد : 14 الإثنين , جمادى الثانية, 1438 تاريخ الإصدار : 08 الأحد , ذو القعدة, 1436

الکلمات المفتاحية: Social networks, شبکه‌های اجتماعی, استخراج جامعه, انتشار گرما, PageRank, Community Detection, Heat Diffusion,

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

شبکه‌های اجتماعی در دهه گذشته توسعه سریعی داشته‌اند. استخراج جامعه مسئله مهمی در تحلیل شبکه‌های اجتماعی است. کشف جامعه در شبکه اجتماعی به‌معنای شناسایی مجموعه‌‌ای از گره‌هاست به‌گونه‌ای که اعضای آن‌ بیشترین ارتباط را بایکدیگر و ارتباط کمی با گره‌های خارج از مجموعه دارند. الگوریتم‌ کلاسیک خوشه‌بندی ‌K‌میانه روش کارایی در این حوزه است ولی این الگوریتم حساس به نقاط اولیه ورودی است. برای حل این مشکل دراین پژوهش ابتدا K نقطه ثقل با استفاده از PageRank شناسایی و سپس ساختار جامعه با استفاده از شباهت انتشارگرما وK ‌میانه استخراج می‌شود. با استفاده از شباهت انتشارگرما می‌توان اطلاعات سراسری شبکه را برای هر زوج از رأس‌ها بدست و برای استفاده در شبکه‌های بزرگ و خلوت مناسب است.

المصادر:

[1]         C. C. Aggarwal, An introduction to social network data analytics. Springer US, 2011.

[2]         S. Fortunato, “Community detection in graphs,” Phys. Rep., vol. 486, no. 3–5, pp. 75–174, Feb. 2010.

[3]         T. Lei, H. Liu, and L. Tang, Community detection and mining in social media, vol. 2, no. 1. Morgan & Claypool Publishers, pp. 1–137, 2010.

[4]         Y. Xu, X. Guo, J. Hao, J. Ma, R. Y. K. Lau, and W. Xu, “Combining social network and semantic concept analysis for personalized academic researcher recommendation,” Decis. Support Syst., vol. 54, no. 1, pp. 564–573, 2012.

[5]         L. Tang and H. Liu, “Graph mining applications to social network analysis,” in Managing and Mining Graph Data, ”Springer, pp. 487–513, 2010.

[6]         G. Palla, I. Derényi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, vol. 435, no. 7043, pp. 814–818, 2005.

[7]         J. Abello, M. G. C. Resende, and S. Sudarsky, “Massive quasi-clique detection,” in Theoretical Informatics, Springer, pp. 598–612, 2002.

[8]         M. E. J. Newman, “Modularity and community structure in networks,” Proc. Natl. Acad. Sci., vol. 103, no. 23, pp. 8577–8582, 2006.

[9]         R. Shang, J. Bai, L. Jiao, and C. Jin, “Community detection based on modularity and an improved genetic algorithm,” Phys. A Stat. Mech. its Appl., vol. 392, no. 5, pp. 1215–1231, Mar. 2013.

[10]       H. Jiawei, K. Micheline, and P. Jian, Data Mining concepts and techniques, pp. 452–454, 2012.

[11]       J. MacQueen and others, “Some methods for classification and analysis of multivariate observations,” in Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, ” vol. 1, no. 281–297, p. 14, 1967.

[12]       D. Arthur and S. Vassilvitskii, “k-means++: The advantages of careful seeding,” in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, ” pp. 1027–1035, 2007.

[13]       M. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E, vol. 69, no. 2, 2004.

[14]       M. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. E, vol. 69, no. 6, p. 66133, 2004.

[15]       Y. Jiang, C. Jia, and J. Yu, “An efficient community detection method based on rank centrality,” Phys. A Stat. Mech. its Appl., vol. 392, no. 9, pp. 2182–2194, May 2013.

[16]       V. D. Blondel, J.-L. Guillaume, E. Lefebvre, and R. Lambiotte, “Fast unfolding of communities in large networks,” J. Stat. Mech. Theory Exp., 2008.

[17]       M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proc. Natl. Acad. Sci., vol. 105, no. 4, pp. 1118–1123, 2008.

[18]       A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, “Finding statistically significant communities in networks,” PLoS One, vol. 6, no. 4, p. e18961, 2011.

[19]       U. N. Raghavan, S. Kumara, and R. Albert, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E, vol. 76, no. 3, 2007.

[20]       M. Belkin and P. Niyogi, “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation,” vol. 15, no. June, pp. 1373–1396, 2003.

[21]       H. Yang, I. King, and M. R. Lyu, “DiffusionRank:A Possible Penicillin for Web Spamming,” pp. 431–438, 2007.

[22]       S. Aarthi and S. Sampath, “A Heat Diffusion Method for Mining Web Graphs for Recommendations Using Recommendation Algorithm,” Int. J. Eng. Res. Technol., vol. 2, no. 8, pp. 961–966, 2013.

[23]       H. Ma, I. King, S. Member, and M. R. Lyu, “Mining Web Graphs for Recommendations,” vol. 24, no. 6, pp. 1051–1064, 2012.

[24]       H. Ma, H. Yang, M. R. Lyu, and I. King, “Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection,” pp. 233–242, 2008.

[25]       M. E. J. Newman, “Analysis of weighted networks,” Phys. Rev. E, vol. 70, no. 5, p. 56131, 2004.

[26]       A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani, “The architecture of complex weighted networks,” Proc. Natl. Acad. Sci. U. S. A., vol. 101, no. 11, pp. 3747–3752, 2004.

[27]       T. Opsahl, F. Agneessens, and J. Skvoretz, “Node centrality in weighted networks: Generalizing degree and shortest paths,” Soc. Networks, vol. 32, no. 3, pp. 245–251, 2010.

[28]       T. Pagerank, C. Ranking, and B. Order, “The pagerank citation ranking: bringing order to the web,” Tech. Report, Stanford Univ., pp. 1–17, 1999.

[29]       N. Duhan, A. K. Sharma, and K. K. Bhatia, “Page Ranking Algorithms:A Survey,” in IEEE International Advance Computing Conference, no. March, pp. 6–7, 2009.

[30]       A. Jain, R. Sharma, G. Dixit, and V. Tomar, “Page Ranking Algorithms in Web Mining, Limitations of Existing Methods and a New Method for Indexing Web Pages,” in 2013 International Conference on Communication Systems and Network Technologies, pp. 640–645, 2013.

[31]       Q. Shambour and J. Lu, “A trust-semantic fusion-based recommendation approach for e-business applications,” Decis. Support Syst., pp. 38–41, 2012.

[32]       W. W. Zachary, “An information flow model for conflict and fission in small groups,” J. Anthropol. Res., vol. 33, pp. 452–473, 1977.

[33]       D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations,” Behav Ecol Sociobiol, vol. 54, no. 4, pp. 396–405, Sep. 2003.

[34]       D. E. Knuth, The Stanford GraphBase: a platform for combinatorial computing, vol. 4. Addison-Wesley Reading, pp. 1–3, 1993.

[35]       V. Krebs, “http:www.orgnet.com,” ,2014.

[36]       M. Girvan and M. E. J. Newman, “Community structure in social and biological networks.,” Proc. Natl. Acad. Sci. U. S. A., vol. 99, no. 12, pp. 7821–6, Jun. 2002.

[37]       L. A. Adamic and N. Glance, “The political blogosphere and the 2004 US election: divided they blog,” in Proceedings of the 3rd international workshop on Link discovery, pp. 36–43, 2005.

[38]       J. Vlasblom and S. J.Wodak, “Markov clustering versus affinity propagation for the partitioning of protein interaction graphs,” BMC Bioinformatics, Oct. 2009.