عنوان

کشف اجتماع با استفاده از خوشه‌بندی گراف‌های وزن‌دار در محیط شبکه‌های اجتماعی

Number

‭۱۸۴۹۶پ‬

.Language of Text, Soundtrack etc

per

Title Proper

کشف اجتماع با استفاده از خوشه‌بندی گراف‌های وزن‌دار در محیط شبکه‌های اجتماعی

First Statement of Responsibility

/هاله توکلی سردرودی

Name of Publisher, Distributor, etc.

: برق کامپیوتر

Date of Publication, Distribution, etc.

، ‮‭۱۳۹۶‬

Name of Manufacturer

، افشاری

Text of Note

چاپی

Dissertation or thesis details and type of degree

کارشناسی ارشد

Discipline of degree

مهندسی کامپیوتر گرایش نرم‌افزار

Date of degree

‮‭۱۳۹۶/۱۱/۰۳‬

Body granting the degree

تبریز

Text of Note

امروزه شبکه‌های اجتماعی، با صدها میلیون کاربر، به عنوان ابزار قدرتمند جهت هدایت جریان اطلاعات محسوب می‌شوند .یکی از موارد حائز اهمیت در تحلیل شبکه‌های اجتماعی، بحث کشف اجتماع است .اجتماع، مجموعه‌ای از گره‌ها است که دارای ارتباطات داخلی فراوانی هستند و ارتباطات اندکی با بیرون از اجتماع دارند .از جمله کاربردهای کشف اجتماع می‌توان به استخراج دقیق‌تر لیست کالاهای پیشنهادی در فرآیند خرید اینترنتی و یافتن علایق مشترک در بین اعضاء یک اجتماع اشاره کرد .برای استخراج این اطلاعات از شبکه‌های واقعی باید به دنبال شبکه‌های اجتماعی با مقیاس بزرگ و وزن‌دار باشیم .به این دلیل که در دنیای واقعی بیشتر شبکه‌ها دارای اطلاعات وزن‌دار هستند و اطلاعات ارزشمندی را در خود دارند .تاکنون روش‌های بسیاری برای کشف اجتماع پیشنهاد شده است .اما بیشتر آنها یا برای گراف‌های وزن‌دار و بزرگ، به‌دلیل پیچیدگی محاسباتی بالا، مناسب نیستند یا گسترش آنها به گراف‌های وزن‌دار سخت است .در این پایان‌نامه روشی نوین برای کشف اجتماع با استفاده از خوشه‌بندی گراف‌های وزن‌دار در محیط شبکه‌های اجتماعی ارائه گردیده است .در این تحقیق با اتکا به الگوریتم کلونی زنبور عسل و الگوریتم کشف اجتماع مبتنی بر جذابیت‮‭(ABCD)‬ ، عملیات کشف اجتماع در گراف‌های وزن‌دار و با مقیاس بزرگ انجام شده است .روش پیشنهادی در دو مرحله اصلی انجام شده است .در ابتدای کار مجموعه داده را که شامل گره و یال است و نشان دهنده رابطه دوستی بین افراد است، را به عنوان ورودی به الگوریتم کلونی زنبور عسل می‌دهیم .و سپس با استفاده از این الگوریتم تعدادی خوشه تولید می‌کنیم .در مرحله دوم عملیات وزن‌دهی به گره‌ها و یال‌ها را انجام می‌دهیم .در مرحله آخر خوشه‌های به‌دست آمده از الگوریتم کلونی زنبور عسل را به عنوان ورودی به الگوریتم ‮‭ABCD‬ می‌دهیم .الگوریتم ‮‭ABCD‬ یک الگوریتم سلسله‌مراتبی پایین به بالا است .که بعد از دریافت خوشه‌ها به عنوان ورودی، بقیه عملیات خوشه‌بندی و کشف اجتماع را انجام می‌دهد .آزمایش‌ها بر روی مجموعه داده ساخت مولف و نیز مجموعه داده‌های واقعی دلفین و فیس‌بوک تست شده است .ارزیابی با معیار ماژولاریتی نشان می‌دهدکه الگوریتم پیشنهادی برای شبکه فیس‌بوک که یک مجموعه داده با مقیاس بزرگ است، با مقدار ماژولاریتی ‮‭۰.۳۲۲۸‬ به خوبی می‌تواند عملیات کشف اجتماع را در شبکه‌های وزن‌دار و بزرگ انجام دهد

Text of Note

Nowadays, social networks, with hundreds of users, are considered as the powerful tools for managing the flow of information. One of the important issues in analyzing the social networks is the discovery of the community. The community is a set of nodes which have plenty of internal communication and have little connection outside the community. Among the community discovery applications, it is possible to accurately extract the list of the suggested products in the online shopping process and find the common interests among the members of a community. To extract this information from real networks, we need to look for large scale and weighted social networks. Because in the real world, most networks have weighted data and valuable information. Yet, many ways have been proposed to discover the community. But most of them are not suitable for large and weighted graphs because of their high computational complexity, or difficult to extend into weighted graphs. In this thesis, a new method for discovering a community is presented using the clustering of the weighted graphs in a social networking environment. In this research, based on the Bee colony algorithm and the attractiveness-based community detection (ABCD) algorithm, community discovery operations are performed on the weighted and large-scale graphs. The proposed method is carried out in two main stages. At the beginning, we give the dataset, which is consisted of the nodes and edges and it represents the friendship between individuals, as an input to the honey colony algorithm. And then, using this algorithm, we generate a number of clusters. In the second step we perform weighted operations on nodes and edges. In the final stage, we give the clusters obtained from the Bee colony algorithm to the ABCD algorithm as input. The ABCD algorithm is a bottom-up hierarchy algorithm. After receiving clusters as inputs, the rest of the clustering and community discovery operations are executed. Experiments have been tested on the author's dataset as well as the actual datasets like Dolphin and Facebook. Evaluation with the modularity criterion shows that the proposed algorithm for the Facebook network, which is a large-scale dataset, with the modularity of 0.3228 can appropriately detect the community in the weighted and large networks

توکلی سردرودی، هاله

فیضی‌درخشی، محمد رضا، استاد راهنما

اقدسی،سید هادی، استاد مشاور

Public note

سیاه و سفید

نمایه‌سازی قبلی