Photo Photo Photo Photo Photo Photo
Print
E-mail
Computer science: Community Tracking in Time Evolving Networks: An Evolutionary Multi-objective Approach

 

Community Tracking in Time Evolving Networks: An Evolutionary Multi-objective  Approach

Haidar S. Khoder,  Bara A. Attea*

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

Abstract

     In real world, almost all networks evolve over time. For example, in networks of friendships and acquaintances, people continually create and delete friendship relationship connections over time, thereby add and draw friends, and some people become part of new social networks or leave their networks, changing the nodes in the network. Recently, tracking communities encountering topological shifting drawn significant attentions and many successive algorithms have been proposed to model the problem. In general, evolutionary clustering can be defined as clustering data over time wherein two concepts: snapshot quality and temporal smoothness should be considered. Snapshot quality means that the clusters should be as precise as possible during the current time step. Temporal smoothness, on the other hand, means that the clusters should not changed dramatically between successive time steps. In this paper, a multi-objective optimization model, based on internal community density as snapshot metric, is proposed and compared with the state-of-the-art modularity based model. Both models are then used to solve the community tracking problem in dynamic social network. The problem, in both models, is stated as a multi-objective optimization problem and the decomposition based multi-objective evolutionary algorithm is used to solve the problem. Experimental results reveals that the proposed model significantly outperforms the already existing model in the ability of tracking more shifted communities.

 

Keywords:  Evolutionary clustering; evolutionary network analysis; dynamic social networks; graph partitioning; social network analysis.

 

تعقب المجتمع في الشبكات الاجتماعية المتغيره مع مرور الزمن: طريقة تطورية متعددة الأهداف

حيدر سفير خضير، براء علي عطية*

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

الخلاصة           

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



alt

 

 

 

S5 Box

Login



Register

*
*
*
*
*

Fields marked with an asterisk (*) are required.