�ݺ�ߣ

‫کامپیوتر‬ ‫مهندسی‬ ‫دانشکده‬
‫جوامع‬ ‫ساختار‬ ‫تشخیص‬ ‫بهبود‬ ‫برای‬ ‫محلی‬ ‫وجوی‬‫جست‬ ‫با‬ ‫ژنتیک‬ ‫الگوریتم‬ ‫یک‬
A Genetic Algorithm with Local Search Strategy for Improved Detection of Community Structure
‫پویا‬ ‫پیچیده‬ ‫های‬‫شبکه‬ ‫درس‬ ‫ارایه‬
‫نصرآبادی‬ ‫ذاکری‬ ‫مرتضی‬
‫استاد‬:
‫رحمانی‬ ‫حسین‬ ‫دکتر‬
‫اردیبهشت‬98

‫ارائه‬‫در‬‫یک‬‫نگاه‬
.IV‫‌ها‬‫ش‬‫آزمای‬
•‫شبکه‬Zachary
•‫شبکه‬Les Miserables
•‫شبکه‬Bottlenose Dolphin
•‫مقایسه‬‫با‬‫دیگر‬‫‌ها‬‫ش‬‫رو‬
.V‫‌گیری‬‫ه‬‫نتیج‬
•‫مسائل‬‫باز‬‫و‬‫کارهای‬‫آتی‬
.I‫مقدمه‬
•‫تشخیص‬‫جوامع‬
•‫شرح‬‫مسئله‬
.II‫کارهای‬‫مرتبط‬
•‫تشخیص‬‫جوامع‬‫با‬‫معیار‬‫‌ای‬‫ه‬‫پیمان‬‫بودن‬
.III‫روش‬‫پیشنهادی‬
•‫الگوریتم‬‫ژنتیک‬‫با‬‫‌وجوی‬‫ت‬‫جس‬‫محلی‬
•(GAS)
‫جوامع‬ ‫ساختار‬ ‫تشخیص‬ ‫بهبود‬ ‫برای‬ ‫محلی‬ ‫وجوی‬‫جست‬ ‫با‬ ‫ژنتیک‬ ‫الگوریتم‬ ‫یک‬-‫ذاکری‬ ‫مرتضی‬2

‫تشخیص‬‫جوامع‬
•‫تعیین‬‫‌هایی‬‫ه‬‫گرو‬‫در‬‫یک‬‫شبکه‬
•‫ارتباط‬‫‌ها‬‫ه‬‫گر‬‫در‬‫داخل‬‫‌ها‬‫ه‬‫گرو‬‫زیاد‬
•‫ارتباط‬‫‌ها‬‫ه‬‫گر‬‫بین‬‫‌ها‬‫ه‬‫گرو‬‫کم‬
•‫کاربردها‬
•‫بازسازی‬‫‌افزار‬‫م‬‫نر‬(W.-F. Pan et al, 2013)
•‫‌های‬‫م‬‫سیست‬‫‌کننده‬‫ه‬‫توصی‬(P. Moradi et al, 2015)
•‫مهندسی‬‫معکوس‬(S. Mancoridis et al, 1999)
‫مقـدمه‬‫کارهای‌مرتبط‬‌‫روش‌پیشنهادی‬(GAS)‫‌گیری‬‫ه‬‫نتیج‬
‫‌ها‬‫ش‬‫آزمای‬
1
2
3
4
5
6

‫شرح‬‫مسئله‬
•‫تشخیص‬‫جوامع‬‫یک‬‫مسئله‬NP-Hard(L. Shuzhuo et al, 2010)
•‫تعداد‬‫کل‬‫جوامع‬‫ممکن‬‫در‬‫یک‬‫گراف‬‫با‬n‫گره‬:
𝑂(𝑛 𝑛)
•‫حل‬‫تقریبی‬‫مسئله‬
•‫‌های‬‫ش‬‫رو‬‫‌جوی‬‫ت‬‫جس‬‫اکتشافی‬(Heuristic)
‫مقـدمه‬‫کارهای‌مرتبط‬‌‫روش‌پیشنهادی‬(GAS)‫‌گیری‬‫ه‬‫نتیج‬ ‫‌ها‬‫ش‬‫آزمای‬

‫کارهای‬‫مرتبط‬
‫‌های‌سنتی‬‫ش‬‫رو‬‫‌های‌فعلی‬‫ش‬‫رو‬
‌‫عدم‌استفاده‌از‬
‫‌ای‌ب‬‌‫ه‬‫معیار‌پیمان‬‫ودن‬
‫‌بندی‌سلس‬‫ه‬‫خوش‬‌‫له‬
‫مراتبی‬
‫‌های‌تکام‬‫م‬‫الگوریت‬‌‫لی‬
‫مثل‌ژنتیک‬
‌‫استفاده‌از‌معیار‬
‫‌ای‬‫ه‬‫پیمان‬‫بودن‬
‌‫راهبرد‬
‫تقسیم‌باال‬-‫به‬-‫پ‬‫ایین‬
‫راهبرد‬
‫ادغام‌پایین‬-‫به‬-‫باال‬
‫در‌نظر‌نگرفتن‌دانش‬
‌‫نهفته‌در‌ماتریس‬
‫مجاورت‬
‫تشخیص‌جوامع‬
Michelle Girvan Mark Newman
‫تعیین‌تعداد‌جوام‬‫ع‬

‫تعریف‬‫جامعه‬
• 𝐺 = (𝑉, 𝐴)
• 𝜏 𝑉 = 𝑉1, 𝑉2, … , 𝑉𝑚
• 𝑉𝑖 ∈ 𝑉 , 𝑉𝑖 ≠ ∅ , 𝑓𝑜𝑟 𝑖 = 1 𝑡𝑜 𝑚
• ‫ڂ‬𝑖=1
𝑚
𝑉𝑖 = 𝑉 , 𝑉𝑖 ∩ 𝑉𝑗 = ∅
• 𝐴 =
0 0 1 0 0 0
0 0 1 0 0 0
1 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
, 𝐴 = σ𝑖=1
𝑛
σ 𝑗=1
𝑛
𝑎𝑖𝑗 = 12
1
2
3
4
5
6

‫نمایش‬‫جامعه‬
• 𝐴 𝑝,𝑞 = 𝑎𝑖𝑗 , 𝑖 ∈ 𝑝 , 𝑗 ∈ 𝑞
• 𝐴 𝑝,𝑞 =
4 5 6
1 0 0 0
2 0 0 0
3 1 0 0
• ||𝐴 𝑝,𝑞|| = σ𝑖∈𝑉𝑝
σ 𝑗∈𝑉𝑞
𝑎𝑖𝑗
• ||𝐴 𝑝,𝑞|| = 1
• ||𝐴 𝑝,𝑝|| = 4, ||𝐴 𝑞,𝑞|| = 6
1
2
3
4
5
6
1 2 3 4 5 6
1 0 0 1 0 0 0
2 0 0 1 0 0 0
3 1 1 0 1 0 0
4 0 0 1 0 1 1
5 0 0 0 1 0 1
6 0 0 0 1 1 0

‫معیار‬‫ای‬‫پیمانه‬‫بودن‬
• 𝑒 𝑝,𝑞 = 𝑒 𝑞,𝑝 =
||𝐴 𝑝,𝑞||
||𝐴||
=
1
12
• 𝑒 𝑝,𝑝 =
||𝐴 𝑝,𝑝||
||𝐴||
=
4
12
=
1
3
• 𝑒 𝑞,𝑞 =
||𝐴 𝑞,𝑞||
||𝐴||
=
6
12
=
1
2
➢𝑄 = σ 𝑝=1
𝑚
[𝑒 𝑝,𝑝 − σ 𝑞=1
𝑚
𝑒 𝑝,𝑞
2
]
• 𝑄 = σ 𝑝=1
𝑚
𝑒 𝑝,𝑝 − σ 𝑝=1
𝑚 σ 𝑞=1
𝑚
𝑒 𝑝,𝑞
2
• 𝑄 =
4
12
+
6
12
−
1
12
2
+
1
12
2
• =
5
6
−
1
72
≈ 0.819
1
2
3
4
5
6
1 2 3 4 5 6
1 0 0 1 0 0 0
2 0 0 1 0 0 0
3 1 1 0 1 0 0
4 0 0 1 0 1 1
5 0 0 0 1 0 1
6 0 0 0 1 1 0

‫تابع‬‫هدف‬
• 𝜏 𝑉 = 𝑉1, 𝑉2, … , 𝑉𝑚 ∈ 𝐼
➢ 𝜏∗
𝑉 = max Q 𝜏 𝑉
• 𝑠. 𝑡. 𝜏 𝑉 = 𝑉1, 𝑉2, … , 𝑉𝑚 ∈ 𝐼
1(‫کدگذاری‬‫مسئله‬‫و‬‫جمعیت‬‫اولیه‬
2(‫عملگر‬‫تقاطع‬(Cross-over)
3(‫عملگر‬‫جهش‬(Mutation)
4(‫عملگر‬‫‌وجوی‬‫ت‬‫جس‬‫محلی‬‫و‬‫عملگر‬‫انتخاب‬‫محلی‬
5(‫انتخاب‬‫نسل‬‫بعدی‬
‌‫فضای‌کل‬
‫‌ها‬‫ل‬‫‌ح‬‫ه‬‫را‬

‫کدگذاری‬‫مسئله‬‫و‬‫جمعیت‬‫اولیه‬
1 2 3 4 5 6
1 1 2 2 3 3
1
2
3
4
5
6
𝜏 = 𝜏1 𝑉 , 𝜏2 𝑉 , … , 𝜏 𝑔 𝑉 , ⊂ 𝐼
𝜏𝑖 𝑉 =
1 2 3 4 5 6
1 1 1 2 2 2
1 2 3 4 5 6
1 3 1 2 3 3
𝜏1 𝑉 =
𝜏2 𝑉 =

‫تقاطع‬(Cross-over)
•‫انتخاب‬‫دو‬‫کروموزم‬(‫ساختار‬‫جامعه‬)
•‫‌صورت‬‫ه‬‫ب‬‫تصادفی‬
•‫انتخاب‬‫یک‬‫گره‬‫در‬‫کروموزم‬‫اول‬
•‫تغییر‬‌‫ه‬‫جامع‬‫‌های‬‫ه‬‫گر‬‫نظیر‬‫در‬‫کرومو‬‫زم‬
‫دوم‬‫به‬‌‫ه‬‫جامع‬‫کروموزم‬‫اول‬
•‫با‬‫احتمال‬𝑃𝑐
•‫ادامه‬‫فرایند‬‫تا‬‫ایجاد‬‫جمعیت‬‫جدید‬
1 2 3 4 5 6
1 1 1 2 2 2
1 2 3 4 5 6
1 3 1 2 3 3
𝜏1 𝑉 =
𝜏2 𝑉 =
1 2 3 4 5 6
1 3 1 2 2 2

‫جهش‬(Mutation)
•‫انتخاب‬‫یک‬‫کروموزم‬
•‫با‬‫احتمال‬𝑃𝑚
•‫انتخاب‬‫دو‬‫گره‬‫از‬‫کروموزم‬‫انتخابی‬
•‫جایگزین‬‫کردن‬‫مقدار‬‫جامعه‬‫گره‬‫اول‬‫ب‬‫ا‬
‫جامعه‬‫گره‬‫دوم‬
1 2 3 4 5 6
1 3 1 2 3 3
𝜏2 𝑉 =
1 2 3 4 5 6
1 1 1 2 3 3
𝜏2 𝑉 =

‫وجو‬‫جست‬‫و‬‫انتخاب‬‫محلی‬
•‫انتخاب‬‫یک‬‫کروموزم‬
•‫همه‬‫‌ها‬‫م‬‫کرموزو‬‫‌نوبت‬‫ه‬‫ب‬‫انتخاب‬‫‌شوند‬‫ی‬‫م‬!
•‫ایجاد‬𝑛𝑙‫کپی‬‫از‬‫کروموزم‬‫انتخابی‬
•‫برای‬‫هر‬‫کپی‬‫ایجاد‬‫شده‬:
•‫انتخاب‬‫دو‬‫گره‬‫همسایه‬‫در‬‫شبکه‬
•‫قرار‬‫دادن‬‫هر‬‫دو‬‫گره‬‫در‬‫یک‬‫جامعه‬
•‫انتخاب‬‫محلی‬
•‫جایگزین‬‫کردن‬‫کروموزم‬‫اولیه‬‫با‬‫بهترین‬‫کپی‬
(‫از‬‫نظر‬‫تابع‬‫هدف‬)
1 2 3 4 5 6
1 1 2 2 3 3
𝜏𝑖 𝑉 =
1
2
3
4 5 6
1 2 3 4 5 6
1 1 2 2 3 3
1 2 3 4 5 6
1 1 2 2 3 3
𝜏𝑖1 𝑉 =
𝜏𝑖2 𝑉 =
1
2
3
4 5 6

‫انتخاب‬‫نسل‬‫بعدی‬
•‫انتخاب‬roulette-wheel(J.E. Baker, 1987)
•‫دادن‬‫شانس‬‫بیشتر‬‫به‬‫‌های‬‫م‬‫کروموز‬‫بهتر‬‫برای‬‫انتخاب‬‫شدن‬
‫شماره‌کروموزم‬ 1 2 3 4 5 6 7 8 9 10 11
‫مقدار‌برازش‬ 2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0
‫احتمال‌انتخاب‌شدن‬ 0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.02 0.0
‫تعداد‬(g=6)‫تصادفی‬ ‫عدد‬ 0.81 0.32 0.96 0.01 0.65 0.42

‫چیدمان‬‫ها‬‫آزمایش‬
•‫پارامترهای‬‫الگوریتم‬GAS
•‫‌سازی‬‫ه‬‫پیاد‬‫و‬‫اجرا‬
‫مقدار‬ ‫نماد‬ ‫پارامتر‬
20 g ‫جمعیت‌اولیه‬
4 𝑛𝑙 ‌‫تعداد‌کپی‌در‬‫‌وجو‬‫ت‬‫جس‬‫و‌انتخاب‌محلی‬
0.8 𝑃𝑐 ‫احتمال‌تقاطع‬
0.1 𝑃𝑚 ‫احتمال‌جهش‬
3000 𝑁𝑖 ‫تعداد‌تکرار‬
100 𝑁𝑐 ‌‫تعداد‬‫‌های‬‫م‬‫کروموز‬‌‫بهینه‬(‫غالب‬‌)‫‌داری‬‫ه‬‫نگ‬‌‫شده‬
(‫در‌هر‌تکرار‌از‌الگوریتم‬)
‫توضیحات‬ ‫مشخصه‬
MATLAB 7.0 ‫‌نویسی‬‫ه‬‫زبان‌برنام‬
IntelR CoreTM 2 2.00 GHz ‫پردازنده‬

‫ارزیابی‬‫روش‬‫پیشنهادی‬
•‫شبکه‬Zachary

•‫شبکه‬Les Miserables

•‫شبکه‬Bottlenose Dolphin

‫مقایسه‬‫معیار‬‫ای‬‫پیمانه‬‫بودن‬
•‫مقایسه‬‫معیار‬Q‫در‬GAS‫با‬‫سه‬‫روش‬،‫دیگر‬‫روی‬15‫شبکه‬‫و‬‫طی‬40‫بار‬‫اجرا‬

‫گیری‬‫نتیجه‬
.I‫افزودن‬‫‌وجوی‬‫ت‬‫جس‬‫محلی‬‫به‬‫الگوریتم‬‫ژنتیک‬‫منجربه‬‫بهبود‬(‫افزایش‬‫پی‬‫‌ای‬‫ه‬‫مان‬
‫بودن‬)‫تشخیص‬‫جوامع‬‫‌گردد‬‫ی‬‫م‬.
•‫استفاده‬‫از‬‫دانش‬‫پیشین‬‫موجود‬‫در‬‫شبکه‬
•‫اهمیت‬‫دادن‬‫به‬‫پدیده‬‫جهان‬‫کوچک‬‫در‬‫‌های‬‫ه‬‫شبک‬‫واقعی‬
.II‫عملگر‬‫‌وجوی‬‫ت‬‫جس‬‫محلی‬‫زمان‬‫اجرای‬‫الگوریتم‬‫را‬‫افزایش‬‫‌دهد‬‫ی‬‫م‬.
•‫مرتبه‬‫زمانی‬‫الگوریتم‬‫ژنتیک‬‫معمولی‬‫در‬‫تشخیص‬‫جوامع‬𝑂 𝑛2‫است‬.
•‫مرتبه‬‫زمانی‬‫الگوریتم‬GAS‫برابر‬𝑂 𝑛2
𝑛𝑙‫است‬.
•‫برای‬‫‌های‬‫ه‬‫شبک‬‫بزرگ‬(n > 1000)‫مناسب‬‫نیست‬.

‫مسائل‬‫باز‬‫و‬‫کارهای‬‫آتی‬
.I‫استفاده‬‫از‬‫عملگرهای‬‫‌وجوی‬‫ت‬‫جس‬‫محلی‬‫مختلف‬(M. Moradi et al, 2019)
.II‫استفاده‬‫از‬‫چندین‬‫تابع‬‫هدف‬(M. Moradi et al, 2019)
.III‫استفاده‬‫از‬‫الگوریتم‬‫ژنتیک‬‫برای‬‫تشخیص‬‫جوامع‬‫همپوشان‬‫در‬‫شبکه‬
.IV‫استفاده‬‫از‬‫الگوریتم‬‫ژنتیک‬‫برای‬‫تشخیص‬‫جوامع‬‫در‬‫‌های‬‫ه‬‫شبک‬‫چند‬‫الیه‬
.V‫استفاده‬‫از‬‫دیگر‬‫‌های‬‫ش‬‫رو‬‫‌سازی‬‫ه‬‫بهین‬‫مثل‬‫یادگیری‬‫ژرف‬‫در‬‫تشخیص‬‫جوامع‬

‫مراجـع‬
o W.-F. Pan, B. Jiang, B. Li, Refactoring software packages via community detection in complex
software networks, Int. J. Autom. Comput. 10 (2013) 157–166.
oP. Moradi, S. Ahmadian, F. Akhlaghian, “An effective trust-based recommendation method using
a novel graph clustering algorithm”, Physica A 436 (2015) 462–481.
oS. Mancoridis, B. S. Mitchell, Y. Chen and E. R. Gansner, “Bunch: a clustering tool for the recovery
and maintenance of software system structures,” Proceedings IEEE International Conference on
Software Maintenance - 1999 (ICSM'99). 'Software Maintenance for Business Change' (Cat.
No.99CB36360), Oxford, England, UK, 1999, pp. 50-59.
oL. Shuzhuo, C. Yinghui, D. Haifeng, and M. W., Feldman, “A genetic algorithm with local search
strategy for improved detection of community structure,” Complexity 15 (2010).
oJ.E. Baker, “Reducing bias and inefficiency in the selection algorithm,” In [ICGA2], pp. 14-21,
1987.

‫مراجـع‬
o M. Moradi and S. Parsa, “An evolutionary method for community detection using a novel local
search strategy,” Phys. A Stat. Mech. its Appl., vol. 523, pp. 457–475, 2019.

‫ش‬ ‫توجه‬ ‫از‬ ‫سپاس‬ ‫با‬‫ما‬
Photo: Spring in IUST )2017( © Morteza Zakeri
‫ن‬ ‫پرسیدن‬ ‫سؤال‬ ‫از‬ ‫دست‬ ‫که‬ ‫است‬ ‫این‬ ‫مهم‬ ‫مسئله‬‫کشید؛‬
‫داشتن‬ ‫وجود‬ ‫برای‬ ‫است‬ ‫دلیلی‬ ‫کنجکاوی‬.
‫انیشتین‬ ‫آلـبرت‬
m o r t e z a _ z a ke r i @ c o m p . i u s t . a c . i r

�ݺ�ߣ

Community Detection with Genetic Algorithm

More Related Content

Community Detection with Genetic Algorithm