Photo Photo Photo Photo Photo Photo

Print
E-mail
Computer Science: An Evolutionary Bi-clustering Algorithm for Community Mining in Complex Networks

 

An Evolutionary Bi-clustering Algorithm for Community Mining in Complex Networks

Saja Salah Abdul Emeer*, Saja Hattem Kareem, Baraa Ali Atea

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

Abstract

A network (or formally a graph) can be described by a set of nodes and a set of edges connecting these nodes. Networks model many real-world phenomena in various research domains, such as biology, engineering and sociology. Community mining is discovering the groups in a network where individuals group of membership are not explicitly given. Detecting natural divisions in such complex networks is proved to be extremely NP-hard problem that recently enjoyed a considerable interest. Among the proposed methods, the field of evolutionary algorithms (EAs) takes a remarkable interest. To this end, the aim of this paper is to present the general statement of community detection problem in social networks. Then, it visits the problem as an optimization problem where a modularity-based ( ) and normalized mutual information ( ) metrics are formulated to describe the problem. An evolutionary algorithm is then expressed in the light of its characteristic components to tackle the problem. The presentation will highlight the possible alternative that can be adopted in this study for individual representation, fitness evaluations, and crossover and mutation operators. The results point out that adopting  as a fitness function carries out more correct solutions than adopting the modularity function . Moreover, the strength of mutation has a background role. When coupled with non elite selection, increasing mutation probability could results in better solutions. However, when elitism is used, increasing mutation probability could bewilder the behavior of EA.

Keywords: complex networks, graph co-clustering, EA, NP-hard.

 

خوارزمية تطورية ذات تصنيف ثنائي الأبعاد لكشف الجاليات في الشبكات المعقدة    

سجى صلاح عبد الأمير*, سجى حاتم كريم, براء علي عطية

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

الخلاصة

يمكن وصف الشبكة كمخطط من خلال مجموعة من العقد ومجموعة من الروابط التي تربط هذه العقد. تعتبر الشبكات نموذج لعديد من الظواهر في العالم الحقيقي و في المجالات البحثية المختلفة ، مثل علم الأحياء والهندسة وعلم الاجتماع. الشبكات الاجتماعية  والشبكات البايولوجية، الشبكة العالمية، والإنترنت، وشبكات التعاون وشبكات الطاقة، والفيسبوك والبيئية والاتصالات وشبكات النقل ماهي الا أمثلة .و دراسة هذه الشبكات المعقدة  تشمل باحثين من  تخصصات مختلفة كثيرة، على سبيل المثال ،علوم الكمبيوتر، والهندسة، وعلم الأحياء، والرياضيات، والفيزياء، وعلم الاجتماع, مما يؤدي إلى تشكيل العديد من المجالات المتعددة التخصصات. اكتشاف المجتمع هو اكتشاف المجموعات المرتبطة بالشبكة من حيث انها عضو صريح في الشبكة او لا. ومن بين الطرق المقترحة في هذا المجال الخوارزميات التطورية (EAs) والتي تأخذ اهتماما ملفتا للنظر في الفترة الاخيرة . فالهدف من هذا البحث هو تقديم بيان عام للمشكلة وكشف المجتمعات في الشبكات الاجتماعية و تطمح هذه الرسالة الى النظر للمشكلة كونها مشكلة امثلية  مستندة الى مقياسي  (Q) و(NMI)  واللتان تعتبران مقياسان لوصف المشكلة . ثم يتم التعبير عن الخوارزمية  التطورية في ضوء العناصر المميزة لها لمعالجة هذه المشكلة. و سوف يتم  تسليط الضوء على البدائل الممكنة التي يمكن اعتمادها في هذه الدراسة لتمثيل الأفراد. وتشير النتائج إلى أن اعتماد NMI بوصفها مقياس لكفاءة الفرد تنفذ حلول أكثر دقة من اعتماد مقياس Q. اضافة لذلك، احتمالية قوة الطفرة (pm) لها دوركبير. عندما يقترن الافراد مع عدم اختيار النخبة منهم، وزيادة احتمال الطفرة يمكن أن يؤدي إلى حلول أفضل. ومع ذلك، عند استخدام النخبة، وزيادة احتمال الطفرة قد يربك سلوك الـ EA.




alt

 

S5 Box

Login



Register

*
*
*
*
*

Fields marked with an asterisk (*) are required.