نوع مقاله : مقاله پژوهشی
نویسندگان
1 دانشجوی دکترای مهندسی صنایع، دانشکده مهندسی صنایع و سیستمهای دانشگاه تربیت مدرس
2 استادیار گروه مهندسی صنایع، دانشکده مهندسی صنایع و سیستمهای دانشگاه تربیت مدرس
چکیده
اجتماعیابی (کشف اجتماعات) یکی از شاخههای نوظهور و پرطرفدار در علم دادهکاوی و تحلیل شبکههای اجتماعی است که کاربردهای فراوانی در کشف و تحلیل اجتماعها در سایتهای اینترنتی، شبکههای زیستی، علمی و پژوهشی و غیره دارد. اجتماعیابی صفحات اینترنتی میتواند بهطور ویژه به مدیران سایتهای اینترنتی در تخصیص پهنای بهینه به شبکه صفحات وب تحت نظارتشان کمک کند. در اکثر روشهای اجتماعیابی موجود فقط از توپولوژی شبکه (ارتباطات، یالها) برای گروهبندی گرهها (صفحات وب) استفاده میشود؛ درحالیکه نتایج پژوهشهای اخیر نشان داده است که اینگونه روشها باید بهگونهای تغییر کند که در آنها علاوه بر توپولوژی، ویژگیهای ذاتی گرهها نیز در فرآیند اجتماعیابی لحاظ شود. ازاینرو در این مقاله برای اولین بار با لحاظ کردنِ همزمانِ ویژگیهای ذاتی صفحات وب و ارتباطات میان آنها، یک مدل ریاضی برای کشف اجتماعات در شبکههای اینترنتی توسعه دادهشده است. روش پیشنهادی این پژوهش بدینصورت است که برای لحاظ کردن ویژگیها در فرآیند اجتماعیابی، ابتدا با استفاده از یک رویکرد ریاضی، میزان شباهتِ صفحات وب به کمک یک سنجه شباهت (مانند جاکارد یا ضریب انطباق) و بردار ویژگیها محاسبه و بهعنوان وزن به یالهای موجود بین آنها در شبکۀ اینترنتی موردنظر افزوده میشود. با این کار عملاً یک شبکه اینترنتی ویژگیدار با یالهای غیر موزون به یک شبکه بدون ویژگی با یالهای موزون تبدیل میشود. سپس با استفاده از یک مدل ریاضی (که مختص شبکههایی با یالهای موزون است)، اجتماعات موجود در این شبکۀ موزون کشف میشود. برای اعتبارسنجی و اثبات کارایی، در قالب آزمونهای فرض آماری ادعاشده است که کیفیت اجتماعات کشفشده توسط رویکرد ریاضی پیشنهادی (که ویژگیهای صفحات وب را لحاظ میکند) بهطور آماری بهتر از مدلهای ریاضی پیشین (که از ویژگیها چشمپوشی میکند) است. نتایج آزمونهای آماری روی شبکه اینترنتی واقعی نشان میدهد که مدل پیشنهادی این پژوهش در حالتی که از معیار جاکارد برای محاسبه میزان شباهت صفحات وب استفاده میکند بهطور معنیداری (با P-value=0.01) باعث کشف اجتماعاتی بهتر در قیاس با مدلهای ریاضی پیشین شده است. همچنین نتایج دیگر آزمونهای آماری نیز نشان میدهد که انتخاب سنجۀ شباهتِ متناسب با ماهیت شبکه، تأثیر بسزایی در میزان کیفیت رویکرد پیشنهادی دارد.
کلیدواژهها
عنوان مقاله [English]
Detecting web communities in attributed internet networks using a mathematical programming approach
نویسندگان [English]
1 Ph.D. Student in Industrial Engineering, Faculty of Industrial and Systems Engineering, Tarbiat Modares University
2 Assistant Prof., Faculty of Industrial and Systems Engineering, Tarbiat Modares University
چکیده [English]
Community detection is one of the emerging and well-known topics in the area of data mining and social network analysis, which has wide variety applications in discovering communities in real-world networks such as biological networks, internet weblogs, scientific and research websites, etc. Web community detection can especially help admins assign the optimal bandwidth to the websites of theirown networks. Most of web community detection approaches only use the network topology to discover the web communities. However, the results of the most recent researches show that traditional community detection methods have to be substantially modified to consider web attributes as well as network topology. Therefore, in this paper, a mathematical programming approach is developed for community detection in attributed internet networks by simultaneously considering both network topology and node attributes. In this approach, first, similarities of web pages are calculated using node attributes and a desired similarity measure and are considered as the weight of the corresponding edges. Then, communities of the resulted weighted network will be detected by the proposed mathematical model. To validate and prove the efficiency, it is hypothesized that the detected communities of the proposed approach have a better quality than that of previous models. Experimental results demonstrate that the proposed approach has the ability to significantly improve the quality of detected web communities, when the model uses the Jaccard index. However, the results of other hypotheses indicate that the correct selection of similarity measure has a significant impact on the quality of the detected communities.
کلیدواژهها [English]