کشف جوامع در شبکه‌های اجتماعی با استفاده از کاوش الگوی تکرارشونده
محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسی
سید احمد موسوی
1
(گروه کامپیوتر)
مهرداد جلالی
2
(دانشگاه آزاد اسلامی، مشهد)
نگین میثاقیان
3
(گروه کامپیوتر)
کلید واژه: Social networks, شبکه‌های اجتماعی, Community Detection, کشف جامعه, کاوش الگوی تکرارشونده, Frequent pattern mining,
چکیده مقاله :
امروزه وب سایت‌های شبکه های اجتماعی به یک منبع غنی از داده های ناهمگون مبدل شده است؛ از این رو تجزیه و تحلیل این داده‌ها می‌تواند منجر به کشف اطلاعات و روابط ناشناخته در این شبکه‌ها شود. کشف جامعه متشکل از گره های مشابه یک چالش مهم در زمینه تجزیه و تحلیل داده های شبکه های اجتماعی است، و به طور گسترده ای در زمینه ساختار گرافی در این شبکه‌ها مورد مطالعه قرار گرفته است. شبکه های اجتماعی اینترنتی علاوه بر ساختار گرافی، حاوی اطلاعات مفیدی از کاربران درون شبکه می‌باشند؛ که استفاده از این اطلاعات می‌تواند منجر به بهبود کیفت کشف جوامع گردد. در این مقاله یک روش به منظور کشف جامعه ارائه شده است که علاوه بر اطلاعات ارتباطی بین گره ها از اطلاعات محتوایی به منظور ارتقا کیفیت کشف جوامع استفاده می‌گردد. این روش یک رویکرد جدید مبتنی بر الگوی تکرار شونده و بر اساس عملیات کاربران در شبکه است و به طور خاص، بر روی شبکه های اجتماعی اینترنتی که در آن کاربران عملیات مورد علاقه خود را انتخاب می کنند، اجرا می‌شود. ابتدا، بر اساس علایق و یا فعالیت های کاربران در شبکه، تعدادی جوامع کوچک متشکل از کاربران مشابه را کشف می کنیم و سپس با استفاده از ارتباطات اجتماعی هر جامعه را گسترش می دهیم. نتایج ارزیابی F-measure بر روی دو مجموعه داده دنیای واقعی (بلاگ کاتالوگ و فلیکر) نشان می‌دهد که روش پیشنهادی منجر به بهبود کیفیت کشف جوامع می شود.
recently, the website social networks provide a rich resource of Heterogeneous data which the analysis of these data can lead to discover unknown information and relations in these networks. The discovery of community including “similar” nodes is a challenging issue in analysis of social networks data, and it has widely studied in the social networking community in the context of the structure of the underlying graphs. The online social networks, additionally having graph structures, include effective information of users within networks, which using this information can lead to improve the quality of communities' discovery. In this paper, for detecting community, a method is provided that in addition to the communication among nodes, to improve the quality of the discovered communities, content information is used, as well. This method is a new approach based on a frequent pattern and the actions of users in the network and in particular, is performed on social networking sites where users select their favorite acts. First, based on Interests and activities of users in networks, we discover some small communities of similar users, and then by using social relations, extend (those) communities. The F-measure evaluated results on two real-world datasets (Blogcatalog and Flicker) demonstrate that the proposed method leads to improvethe quality of community detection.
[1] C. Charu and R. Aggarwal, " Social Network Data Analytic," Springer Science+Business Media, 2011.
[2] S. Wasserman and K. Faust, "Social Network Analysis in the Social and Behavioral Sciences," Social Network Analysis: Methods and Applications, 1994.
[3] M. Coscia, F. Giannott, and D. Pedreschi, "REVIEW A Classification for Community Discovery Methods in Complex Networks," Published online in Wiley Online Library, 2011.
[4] A. E. Mislove, "Online Social Networks: Measurement, Analysis, and Applications to Distributed Information System," Houston, Texa, 2009.
[5] M. Sachan, D. Contractor, A. Faruquie, and L. Venkata, "Using Content and Interactions for Discovering Communities in Social Networks," presented at the International World Wide Web Conference Committee, 2012.
[6] D. Ganley and C. Lampe, "The ties that bind: social network principles in online communities," Decision Support Systems vol. 47, pp. 266-274, 2009.
[7] M. Muhaimenul Adnan, R. Alhaji, and J. Rokne, " Identifying Social Communities by Frequent Pattern Mining," presented at the 13th International Conference Information Visualisation, 2009.
[8] A. Goyal, B. Francesco, and L. Laks V. S, "Discovering Leaders from Community Actions," presented at the CIKM, 2008.
[9] H. Zhuge, "Communities and Emerging Semantics in Semantic Link Network," IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2009.
[10] R. Khorasgani, J. Chen, and O. R. Zaïane, "Top Leaders Community Detection in Information Network," ACM Transactions on Knowledge Discovery from Data, 2010.
[11] R. Kanawati, " Leaders Identification For Community Detection in Complex Network," presented at the IEEE International Conference on Social Computing, 2011.
[12] D. Lu, Q. Li, and S. S. Liao, "A graph-based action network framework to identify prestigious members through member's prestige evolution," Elsevier, 2011.
[13] N. Pathak, C. DeLong, A. Banerjee, and K. Erickson, "Social topics models for community extraction," in 2nd SNA-KDD Workshop, 2008.
[14] D. Zhou, E. Manavoglu, L. Li, C. L. Giles, and H. Zha, " Probabilistic models for discovering e-communities," in International Conference on World Wide Web, 2006.
[15] G. J. Qi, C. C. Aggarwal, and T. Thomas Huang, "Community Detection with Edge Content in Social Media Networks," presented at the 28th International Conference on Data Engineering (ICDE), 2012.
[16] M. Franz, T. Ward, J. S. McCarley, and W. J. Zhu, "Unsupervised and supervised clustering for topic tracking," presented at the ACM SIGIR Conference, 2001.
[17] A. Clauset, M. E. J. Newman, and Moore.C, "Finding community structure in very large networks," In Phys. Rev. E 70, 066111, 2004.
[18] R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, "Trawling the web for emerging cyber-communities," presented at the WWW, 1999.
[19] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, "Statistical properties of community structure in large social and information networks," presented at the WWW, 2008.
[20] V. Satulouri and S. Parthasarathy, "Scalable graph clustering using stochastic flows: Applications to community discovery," presented at the KDD Conference, 2009.
[21] T. Eliassi-Rad, K. Henderson, S. Papadimitriou, and C. Faloutsos, "A hybrid community discovery framework for complex networks,," presented at the SIAM Conference on Data Mining, 2010.
[22] J. M. Hofman and C. H. Wiggins, "A bayesian approach to network modularity," Phys Rev Lett 100, 2008.
[23] A. Clauset, C. Moore, and M. E. J. Newman, "Hierarchical structure and the prediction of missing links in networks.," Nature vol. 453, pp. 98-101, 2008.
[24] S. Borgatti, "Identifying sets of key players in a network," Comput Math Organ Theory, vol. 12, pp. 21-34, 2006.
[25] X. Zhang and D. Dong, "Ways of Identifying the Opinion Leaders in Virtual Communities," International Journal of Business and Management, vol. 3, 2008.
[26] D. Arroyo, "Discovering Sets of Key Players in Social Networks," in Computational Social Networks Analysis, Trends, Tools and Research Advances, ed Computer and Communication Networks Series.: Springer, 2010.
[27] L. C. Freeman, Centrality in Social Networks Conceptual Clarification. Printed in the Netherlands: Elsevier Sequoia S.A., Lausanne, 1978.
[28] W. Jiinlong, X. Conglfu, C. Weidong, and P. Yunhe, "Survey of the Study on Frequent Pattern Mining in Data," presented at the IEEE International Conference on Systems, 2004.
[29] R. Agrawal, "Fast algorithm for mining association rules in large databases," in 20th International Conference on Very Large Data Bases,VLDB, Santiago, Chile, 1994, pp. 487-499.
[30] D. Lu, Q. Li, and S. S. Liao, "A graph-based action network framework to identify prestigious members through member's prestige evolution," DECISION SUPPORT SYSTEMS, 2011.
[31] A. Goyal, B. Francesco, and L. Laks V. S, "Discovering Leaders from Community Actions," in CIKM, 2008.
[32] H. I. Witten and E. Frank, Data Mining:Practical Machine Learning Tools and Techniques (second edition) 2005.
[33] A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," in Phys. Rev., 2004.
[34] M. Newman and M. Girvan, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences, 2002.
[35] M. Feng, J. Li, G. Dong, and L. Wong, "Maintenance of Frequent Patterns," Data Mining and Knowledge Discovery, 2009.
_||_