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

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

مقاله 5، دوره 8، بهار و تابستان 1394، شهریور 1394، صفحه 61-75   

نوع مقاله: مقاله پژوهشی

نویسندگان

ملیحه ابراهیمی نژاد^{* 1}؛ سمانه حسن زاده²؛ مهرداد جلالی³

¹دپارتمان مهندسی کامپیوتر، دانشکده 17 شهریور کرج، دانشگاه فنی و حرفه ای استان البرز، ایران

²2دپارتمان مهندسی کامپیوتر فناوری اطلاعات، موسسه آموزش عالی اقبال لاهوری، مشهد،ایران

³گروه کامپیوتر دانشگاه آزاد اسلامی مشهد

چکیده

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

کلیدواژه‌ها

استخراج جامعه؛ انتشار گرما؛ PageRank؛ شبکه‌های اجتماعی

مراجع

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