Photo Photo Photo Photo Photo Photo
Print
E-mail
Computer Science: Understanding the Role of Positive and Negative Relations for Community Detection Problem in Signed Networks: A New Perspective

 

Understanding the Role of Positive and Negative Relations for Community Detection Problem in Signed Networks: A New Perspective

Huda M. Rada*, Bara’a A. Attea

.              Department of Computer Science, College of Science, University of Baghdad, Baghdad, Iraq.

Abstract

     In real world, almost all networks come out with positive and negative types of relations. The sign could reflect like-dislike, agreement-disagreement, friendship-enmity, and attraction-discouragement. The contribution of this paper is to introduce prototype definitions for both nodes and communities of signed networks according to the distribution of positive and negative signs over the network's links. Two types of nodes (strong and weak) are introduced. Accordingly, three types of communities are declared, these are strong, weak, and irregular (or noisy).  The formulated definitions provide us with a new understanding for the difficulty raised in community detection problem in signed networks. One of the recent state-of-the-art multi-objective detection models (modeled after Liu et al.) is adopted in this study as the optimization function for one of the well-known decomposition based multi-objective evolutionary algorithm (MOEA/D). In the experiments, different levels of complex synthetic networks are generated, characterized, and used as test-bed to explore and evaluate the performance of MOEA/D for solving community detection problem. The results reveal that the accuracy of the network partitioning solutions is increased while increasing the percentage of strong nodes and strong communities and vice versa while increasing percentage of weak nodes and weak and irregular communities.

Keywords: Community detection; graph partitioning; signed relation; social network analysis.

 

فهم دور العلاقات الأيجابية والسلبية في مشكلة كشف المجتمعات للشبكات المؤشرة: منظور جديد

هدى مصطفى رضا*، براء علي عطية

قسم علوم الحاسوب ، كلية العلوم، جامعة بغداد، بغداد، العراق.

الخلاصه

     معظم الشبكات في العالم الحقيقي تأتي بانواع من العلاقات الأيجابية والسلبية   ، يمكن أن تعكس هذة الأشارة  مثلا عدم الاعجاب- الاعجاب ،ألاختلاف والصداقة والعداوة والاحباط ، البصمة في هذ البحث هي تحديد انواع العقد والمجتمعات في الشبكات المؤشرة من خلال توزيع الاشارات الموجبة والسالبة على ارتباطات الشبكات . هناك نوعين من العقد (القوية والضعيفة ). وفقا لذلك  هناك ثلاث من المجتمعات عرفت وهي    القوية والضعيفة والشاذة (الغير النظامية) .التعاريف المصاغة وفرت لنا مفاهيم جديدة للصعوبة التي أثيرت في مشكلة الكشف عن المجتمع في الشبكات المؤشرة  ، و أحد الباحثين الحاليين  في مجال الموديلات المتعددة الاهداف (ليو ) اعتمد في هذة الدراسة  على احد الخوازميات  التطورية متعددة الاهداف في كشف المجتمعات .  وفي التجارب تم انشاء  وتمييز مستويات مختلفة من الشبكات الاصطناعية المعقدة وتقييم أداء خوارزمية كشف المجتمعات متعددة الاهداف للكشف عن المجتمعات في الشبكات المؤشرة ، وتكشف النتائج أن دقة حلول تقسيم الشبكة تزداد مع زيادة نسبة العقد القوية والمجتمعات القوية والعكس بالعكس مع زيادة النسبة المئوية للعقد الضعيفة و المجتمعات الضعيفة وغير النظامية .   



alt

 

S5 Box

Login



Register

*
*
*
*
*

Fields marked with an asterisk (*) are required.