کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5102860 1480091 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Eb&D: A new clustering approach for signed social networks based on both edge-betweenness centrality and density of subgraphs
ترجمه فارسی عنوان
یک رویکرد جدید خوشه بندی برای شبکه های اجتماعی علامت دار براساس مرکزیت بینیت یالی و چگالی زیرگرافها
کلمات کلیدی
خوشه بندی، شبکه علامت دار، بینیت یالی، چگالی
فهرست مطالب مقاله
چکیده

کلمات کلیدی

1.مقدمه

2. اصطلاحات علمی و نمادگذاری ها

3. الگوریتم خوشه بندی Eb&D برای شبکه های علامت دار کلی

3. 1. نتیجه الگوریتم خوشه بندی Eb&D

شکل 1. خطوط توپر، پیوندهای  مثبت، و خطوط نقطه چین، پیوندهای منفی را مشخص می کنند. جوامع واقعی با اشکال مختلف مشخص می شوند (یعنی، مربع ها، لوزی ها و دایره ها).

3. 2. الگوریتم خوشه بندی Eb&D

3. 3. چگونه پارامترهای α وβ را انتخاب کنیم؟

3. 4. پیچیدگی زمانی الگوریتم

شکل 2. نمودار درختی سلسله مراتبی  بعد از استفاده از الگوریتم خوشه بندی Eb&D برای 16 گروه قبیله ای در ساختار اتحاد گاما- گاهوکو. مستطیل قرمز بدین معنی است که آن به تقسیمات بیشتر نیاز ندارد، در حالی که مستطیل های سبز به معنی نیاز بیشتر برای تقسیم بندی است. (برای تفسیر منابع رنگ در این شرح شکل، خواننده به نسخه وب این مقاله ارجاع داده می شود.) 

4. کاربردها و آزمون ها

4. 1. مجموعه داده های مبنا  

شکل 3. خطوط توپر، پیوندهای مثبت، و خطوط نقطه چین، پیوندهای منفی را نشان می دهند. جوامع واقعی با اشکال مختلفی مشخص می شوند (یعنی مربع ها و دایره ها)

4. 2. مجموعه داده های ترکیبی

4. 2. 1. توابع خطا 

شکل 4. نمودار درختی سلسله مراتبی بعد از به کار بردن Eb&D در شبکه رابطه ای ده حزب پارلمان اسلونی در سال 1994

4. 2. 2. نتایج ارزیابی

4. 3. اثرات α و β روی عملکرد Eb&D

4. 4. مزایا و معایب الگوریتم Eb&D 

شکل 5. نرخ خطای  تست شده در مجموعه داده های ترکیبی (با توجه به تعداد رئوس جا افتاده) الگوریتم های Eb&D و S-GRACLUS 

شکل 6. نرخ های خطا در 100 مجموعه داده ها ترکیبی Eb&D با مقادیر پیش فرض و مقادیر تصادفی انتخاب شده α و β (به ترتیب)

5. نتایج
ترجمه چکیده
الگوریتم های خوشه بندی برای شبکه های اجتماعی بدون علامتی که فقط یالهای مثبت دارند به شدت مورد تحقیق و بررسی قرار گرفته اند. اما، زمانی که یک شبکه، روابط دوست داشتن/ دوست نداشتن، عشق/ تنفر، احترام/ عدم احترام، یا اعتماد/ عدم اعتماد دارد، شبکه های اجتماعی بدون علامتی که فقط یال های مثبت دارند، مناسب نیستند. بنابراین، ما این نوع از شبکه ها را به عنوان شبکه های علامت داری مدلسازی می¬کنیم که می توانند هم یالهای منفی و هم یالهای مثبت داشته باشند. شناسایی ساختارهای خوشه ای شبکه¬های علامت دار خیلی سخت تر از شناسایی ساختارهای خوشه ای برای شبکه های بدون علامت است، زیرا نه تنها لازم است که یال های مثبت در درون خوشه ها تا حد ممکن وجود داشته باشند، بلکه لازم است که یالهای منفی بین خوشه ها نیز تا حد ممکن وجود داشته باشند. در حال حاضر، الگوریتم های خوشه بندی کمی برای شبکه های علامت دار داریم، و بیشتر آنها نیازمند تعداد خوشه های نهایی به عنوان ورودی هستند، در حالی که از قبل پیش بینی کردن آن واقعاً سخت است. در این مقاله، ما یک الگوریتم خوشه بندی جدید به نام Eb&D را پیشنهاد می کنیم، که هم بینیت یالها و هم چگالی زیرگرافها برای شناسایی ساختارهای خوشه ای به کار می-روند. یک سیستم تو در توی سلسله مراتبی برای نشان دادن روابط شمول خوشه ها ایجاد می شود. برای نشان دادن اعتبار و کارایی Eb&D، آن را روی چندین شبکه اجتماعی کلاسیک و همچنین صدها مجموعه داده ترکیبی آزمون می کنیم، و همه اینها نتایج بهتری را در مقایسه با روشهای دیگر ارائه می کنند. بزرگترین مزیت Eb&D در مقایسه با روش های دیگر این است که نیاز نیست که تعداد خوشه از قبل مشخص باشند.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات فیزیک ریاضی
چکیده انگلیسی
Clustering algorithms for unsigned social networks which have only positive edges have been studied intensively. However, when a network has like/dislike, love/hate, respect/disrespect, or trust/distrust relationships, unsigned social networks with only positive edges are inadequate. Thus we model such kind of networks as signed networks which can have both negative and positive edges. Detecting the cluster structures of signed networks is much harder than for unsigned networks, because it not only requires that positive edges within clusters are as many as possible, but also requires that negative edges between clusters are as many as possible. Currently, we have few clustering algorithms for signed networks, and most of them requires the number of final clusters as an input while it is actually hard to predict beforehand. In this paper, we will propose a novel clustering algorithm called Eb&D for signed networks, where both the betweenness of edges and the density of subgraphs are used to detect cluster structures. A hierarchically nested system will be constructed to illustrate the inclusion relationships of clusters. To show the validity and efficiency of Eb&D, we test it on several classical social networks and also hundreds of synthetic data sets, and all obtain better results compared with other methods. The biggest advantage of Eb&D compared with other methods is that the number of clusters do not need to be known prior.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Physica A: Statistical Mechanics and its Applications - Volume 482, 15 September 2017, Pages 147-157
نویسندگان
, , , , , ,