طريقة لوفان

طريقة لوفان لاكتشاف المجتمعات هي طريقة تحسين جشعة تهدف إلى استخراج المجتمعات غير المتداخلة من الشبكات الكبيرة التي أنشأها بلونديل وآخرون ^{[ 1 ]} من جامعة لوفان (مصدر اسم هذه الطريقة).

تحسين النمطية

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

في طريقة لوفان لاكتشاف المجتمعات، تُكتشف المجتمعات الصغيرة أولًا بتحسين معامل التجزئة محليًا على جميع العقد، ثم يُجمع كل مجتمع صغير في عقدة واحدة وتُكرر الخطوة الأولى. تشبه هذه الطريقة طريقة كلاوسيت ونيومان ومور السابقة ^{[ 2 ]} التي تربط المجتمعات التي يُؤدي دمجها إلى أكبر زيادة في معامل التجزئة. على الرغم من أن خوارزمية لوفان قادرة على تحديد بنية المجتمع بدقة عندما تكون الأدلة قوية بما يكفي في الشبكات الاصطناعية، وخاصة تلك المأخوذة من نموذج الكتلة العشوائية التجميعية ^{[ 3 ]} ، إلا أنها عُرضة لاكتشاف مجتمعات زائفة في الرسوم البيانية العشوائية ^{[ 4 ]} ، وقد ثبت أنها تُفرط في ملاءمة البيانات التجريبية بشكل منهجي ^{[ 5 ]}^{[ 6 ]} .

وصف الخوارزمية

نمطية التصميم

القيمة التي يجب تحسينها هي المعيارية ، والتي تُعرَّف بأنها قيمة تقع ضمن النطاق $[-1,1]$ يقيس هذا المقياس كثافة الروابط داخل المجتمعات مقارنةً بالروابط بين المجتمعات. ^{[ 1 ]} بالنسبة للرسم البياني الموزون، تُعرَّف النمطية على النحو التالي:

$Q={\frac {1}{2m}}\sum _{i=1}^{N}\sum _{j=1}^{N}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),$

أين:

$A_{ij}$ يمثل وزن الحافة بين العقدتين $i$ و $j$ ؛ انظر مصفوفة التجاور ؛
⁠ $k_{i}$ و $k_{j}$ ⁠ هي مجموع أوزان الحواف المتصلة بالعقدتين $i$ و $j$ على التوالي؛
$يمثل m$ مجموع جميع أوزان الحواف في الرسم البياني؛
$يمثل N$ العدد الإجمالي للعقد في الرسم البياني؛
⁠ $c_{i}$ و $c_{j}$ ⁠ هي المجتمعات التي ينتمي إليها العقدتان $i$ و $j$ ؛ و
$\delta$ دالة دلتا كرونكر :

${\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{إذا كانت }}c_{i}{\text{ و }}c_{j}{\text{ نفس المجموعة}}\\0&{\text{فيما عدا ذلك}}\end{cases}}\end{aligned}}$

بناءً على المعادلة المذكورة أعلاه، يمكن حساب نمطية المجتمع $c على النحو التالي:$ ^{[ 7 ]}

${\begin{aligned}Q_{c}&={\dfrac {1}{2m}}\sum _{i}\sum _{j}A_{ij}\mathbf {1} \left\{c_{i}=c_{j}=c\right\}-\left(\sum _{i}{\dfrac {k_{i}}{2m}}\mathbf {1} \left\{c_{i}=c\right\}\right)^{2}\\&={\frac {\Sigma _{in}}{2m}}-\left({\frac {\Sigma _{tot}}{2m}}\right)^{2}\end{aligned}}$

أين

$\Sigma _{in}$ هو مجموع أوزان الحواف بين العقد داخل المجموعة $ج$ (يتم النظر في كل حافة مرتين)؛ و
$\Sigma _{tot}$ هو مجموع جميع أوزان الحواف للعقد داخل المجتمع (بما في ذلك الحواف التي ترتبط بمجتمعات أخرى).

بما أن العقد في المجتمعات المختلفة لا تساهم في المعيارية $Q$ ، فيمكن كتابتها على النحو التالي:

$Q=\sum _{c}Q_{c}$

خوارزمية طريقة لوفان

تعتمد طريقة لوفان على تكرار مرحلتين. ^{[ 1 ]} في المرحلة الأولى، تُصنّف العُقد إلى مجموعات بناءً على كيفية تغيّر نمطية الرسم البياني عند انتقال عقدة ما بين المجموعات. في المرحلة الثانية، يُعاد تفسير الرسم البياني بحيث تُعتبر المجموعات عُقدًا فردية. يرد شرح مفصل أدناه.

المرحلة الأولى

يتم تخصيص كل عقدة في الشبكة لمجتمعها الخاص.

تبدأ طريقة لوفان باعتبار كل عقدة $v$ في الرسم البياني بمثابة مجتمع مستقل. ويمكن ملاحظة ذلك في الشكل 1، حيث تمثل كل نقطة (تمثل العقد) لونًا فريدًا (يمثل المجتمع الذي تنتمي إليه العقدة).

يتم تجميع العقد في مجتمعات

لكل عقدة $v$ ، ندرس كيف سيؤثر نقل $v$ من مجموعتها الحالية $C$ إلى مجموعة مجاورة $C' على نمطية تقسيم الرسم البياني. في الشفرة الزائفة أدناه، يحدث هذا في حلقة التكرار. نختار المجموعة$ $C'$ التي تشهد أكبر تغيير في النمطية، وإذا كان التغيير موجبًا، ننقل $v$ إلى $C'$ ؛ وإلا نتركها في مكانها. يستمر هذا حتى تتوقف النمطية عن التحسن.

دالة moveNodes(الرسم البياني G، القسم P):  يفعل  old_modularity <- current_modularity_of_partition  لكل قيمة v في V(G)، قم بما يلي:  # ابحث عن المجموعة التي تُسبب أكبر زيادة في قابلية التجزئة عند نقل v إليها  C' <- argmax(delta_Q) # delta_Q هو التغير في المعيارية  إذا كانت دلتا_Q > 0، فإن  انقل v إلى C'  نهاية الشرط  نهاية لـ  تحديث معامل التجزئة الحالي  بينما تكون قيمة التجزئة الحالية أكبر من قيمة التجزئة القديمة  إرجاع P نهاية الدالة

^{[ 8 ]}

تُطبَّق هذه العملية بشكل متكرر ومتسلسل على جميع العُقد حتى يتعذر حدوث أي زيادة في مستوى التجزئة. بمجرد الوصول إلى هذه القيمة القصوى المحلية للتجزئة، تنتهي المرحلة الأولى. يوضح الشكل 2 كيف قد يبدو الرسم البياني في الشكل 1 بعد تكرار واحد للمرحلة الأولى.

المرحلة الثانية

يتم اختزال المجتمعات إلى عقدة واحدة

لكل مجموعة في تقسيم الرسم البياني، تُدمج العقد الفردية المكونة لتلك المجموعة، وتصبح المجموعة نفسها عقدة. تُستخدم الحواف التي تربط المجموعات المختلفة لترجيح الحواف الجديدة التي تربط عقدنا المجمعة.

تُحاكي الشفرة الزائفة هذه العملية، حيث تُعيد الدالة $aggregateGraph$ رسمًا بيانيًا جديدًا، رؤوسه عبارة عن تقسيم للرسم البياني القديم، وحوافه مُحسوبة باستخدام الرسم البياني القديم. لا تُظهر هذه الدالة ترجيح الحواف، ولكن تعديلًا بسيطًا سيُمكّن من تتبع هذه المعلومة.

دالة تجميع الرسم البياني (الرسم البياني G، القسم P):  V <- P  E <- [(A,B) | (x,y) is in E(G), x is in A and A is in P, y is in B and B in P]  أعد الرسم البياني (V، E) نهاية الدالة

^{[ 8 ]}

يوضح الشكل 3 كيف سيبدو الرسم البياني من الشكل 2 بعد تجميعه. هذا الرسم البياني مماثل للرسم البياني في الشكل 1 من حيث أن كل عقدة تُخصص لمجموعة واحدة. ومن هنا، يمكن تكرار العملية لنقل المزيد من العقد إلى المجموعات الموجودة حتى الوصول إلى مستوى مثالي من التجزئة.

يوضح الكود الزائف أدناه كيفية عمل الدالتين السابقتين معًا لإكمال العملية.

دالة لوفين (الرسم البياني G، القسم P): يفعل P <- moveNodes(G, P) تم <- طول(P) == طول(V(G)) # كل مجموعة هي عقدة واحدة، على الرغم من تشغيل moveNodes وإذا لم يتم ذلك، فـ: G <- aggregateGraph(G, P) P <- singletonPartition(G) نهاية الشرط لم يتم الانتهاء نهاية الدالة دالة singletonPartition(Graph G): return [{v} | v is in V(G)] # يتم وضع كل عقدة في مجتمعها الخاص نهاية الدالة

^{[ 8 ]}

تعقيد الخطة

بشكل عام، يُفترض أن طريقة لوفان لها تعقيد زمني قدره $O(n\log {}n)$ يبدو أن ريتشارد بلونديل، المؤلف المشارك للورقة البحثية التي نشرت طريقة لوفان في الأصل، يؤيد هذا المفهوم، ^{[ 9 ]} لكن مصادر أخرى تزعم أن التعقيد الزمني "خطي أساسًا بالنسبة لعدد الروابط في الرسم البياني"، ^{[ 10 ]} مما يعني أن التعقيد الزمني سيكون بدلاً من ذلك $O(m)$ حيث يمثل $m$ عدد الحواف في الرسم البياني. لسوء الحظ، لم ينشر أي مصدر تحليلًا لتعقيد الوقت لطريقة لوفان، لذا تُجرى محاولة لتحليله هنا.

في الشفرة الزائفة أعلاه، تتحكم الدالة $louvain$ في تنفيذ الخوارزمية. من الواضح أنه داخل $louvain$ ، ستُكرر $عملية moveNodes$ حتى يتعذر دمج العقد في مجموعات. يعتمد هذا على عاملين: مدى تحسن نمطية الرسم البياني، وفي أسوأ الأحوال، إذا كان بالإمكان تحسين النمطية مع كل تكرار لـ $louvain$ ، فإن ذلك يعتمد على سرعة اختزال $aggregateGraph للرسم البياني إلى عقدة واحدة.$

إذا لم تتمكن $دالة moveNodes$ في كل تكرار من $خوارزمية louvain$ إلا من نقل عقدة واحدة إلى مجموعة، فلن تتمكن $دالة aggregateGraph$ إلا من تقليل حجم الرسم البياني بمقدار واحد. سيؤدي هذا إلى تكرار خوارزمية $louvain عددًا من المرات$ $يساوي v$ . وبما أن دالة $moveNodes$ تمر على جميع العقد في الرسم البياني، فإن هذا سيؤدي إلى تعقيد زمني قدره ${\mathcal {O}}(n^{2})$ ، حيث $n$ هو عدد العقد.

من غير الواضح ما إذا كان هذا الوضع ممكنًا، لذا ينبغي اعتبار النتيجة المذكورة أعلاه حدًا تقريبيًا. يذكر بلونديل وآخرون في منشورهم الأصلي أن معظم وقت التشغيل يُقضى في التكرارات الأولى للخوارزمية لأن "عدد المجموعات يتناقص بشكل كبير بعد بضع تمريرات فقط". ^{[ 1 ]} يمكن فهم ذلك من خلال النظر في سيناريو حيث تستطيع $دالة moveNodes$ تحريك كل عقدة بحيث تحتوي كل مجموعة على عقدتين. في هذه الحالة، ستُعيد $دالة aggregateGraph$ رسمًا بيانيًا بنصف حجم الرسم الأصلي. إذا استمر هذا، فسيكون وقت تشغيل طريقة Louvain هو $n\log _{2}{n}$ على الرغم من أنه من غير الواضح ما إذا كانت هذه أسوأ حالة، أو أفضل حالة، أو حالة متوسطة، أو لا شيء مما سبق. إضافةً إلى ذلك، لا يوجد ما يضمن أن حجم الرسم البياني سيتقلص بنفس النسبة مع كل تكرار، وبالتالي لا يمكن لأي دالة لوغاريتمية منفردة أن تصف تعقيد الوقت بدقة تامة.

الاستخدامات السابقة

شبكة تويتر الاجتماعية (2.4 مليون عقدة، 38 مليون رابط) بواسطة جوزيب بوجول، وفيجاي إيراميلي، وبابلو رودريغيز: ^{[ 11 ]} يستكشف المؤلفون مشكلة تقسيم الشبكات الاجتماعية عبر الإنترنت على أجهزة مختلفة.
شبكة الهاتف المحمول (4 ملايين عقدة، 100 مليون رابط) بقلم ديريك غرين، ودونال دويل، وبادريغ كانينغهام: ^{[ 12 ]} استراتيجيات تتبع المجتمع لتحديد المجتمعات الديناميكية لشبكات اجتماعية ديناميكية مختلفة.
الكشف عن الأنواع في نموذج ديناميكي قائم على الشبكة. ^{[ 13 ]}

العيوب

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

يُعدّ المجتمع المنفصل داخليًا مثالًا سيئًا للغاية على المجتمعات ذات الاتصال الضعيف. ينشأ هذا النوع من المجتمعات في خوارزمية لوفان عندما تُنقل عقدة كانت تعمل كـ"جسر" بين مجموعتين من العقد في مجتمعها إلى مجتمع جديد، مما يؤدي إلى انقطاع اتصال المجتمع القديم. قد تُنقل العقد المتبقية في المجتمع القديم أيضًا، ولكن إذا كان اتصالها بالمجتمع قويًا بما يكفي رغم إزالة عقدة "الجسر"، فإنها ستبقى في مكانها. كمثال على ذلك، انظر إلى الصورة على اليمين؛ لاحظ كيف أدت إزالة عقدة الجسر، العقدة 0، إلى انقسام المجتمع الأحمر إلى مجموعتين فرعيتين منفصلتين. مع أن هذا هو أسوأ سيناريو، إلا أن هناك مشاكل أخرى أكثر دقة في خوارزمية لوفان قد تؤدي أيضًا إلى مجتمعات ذات اتصال ضعيف، مثل تكوين مجتمعات باستخدام عقد ذات اتصال ضعيف فقط.

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

يتفاقم كل من حد دقة التجزئة ومشكلة المجتمعات ذات الاتصال الضعيف العشوائي مع كل تكرار للخوارزمية. في النهاية، الشيء الوحيد الذي تضمنه خوارزمية لوفان هو عدم إمكانية دمج المجتمعات الناتجة؛ أي أنها منفصلة تمامًا. لتجنب المشاكل الناجمة عن المجتمعات ذات الاتصال الضعيف العشوائي وحد دقة التجزئة، يُنصح باستخدام خوارزمية ليدن ، حيث أن مرحلة التحسين والتعديلات الأخرى المختلفة فيها قد عالجت هذه المشاكل. ^{[ 8 ]}

مقارنة بأساليب أخرى للكشف عن المجتمعات غير المتداخلة

عند مقارنة أساليب تحسين التجزئة، يُعدّ كلٌّ من السرعة وقيمة التجزئة الناتجة معيارين أساسيين. فالسرعة الأعلى أفضل لأنها تدل على كفاءة الأسلوب مقارنةً بغيره، بينما تُعدّ قيمة التجزئة الأعلى مرغوبة لأنها تشير إلى وجود مجتمعات أكثر تحديدًا. وتشمل الأساليب المُقارنة: خوارزمية كلاوسيت ونيومان ومور ^{[ 2 ]} ، وبونز ولاتابي ^{[ 14 ]} ، وواكيتا وتسورومي ^{[ 15 ] .}

مقارنة تحسين النمطية ^{[ 16 ]}
	الكاراتيه	أرشيف	إنترنت	موقع الويب nd.edu	هاتف	موقع ويب المملكة المتحدة - 2005	ويب ويب بيس 2001
العقد/الروابط	34/77	9k/24k	70 ألف/351 ألف	325 ألف/1 مليون	2.6 مليون / 6.3 مليون	39 مليون / 783 مليون	118M/1B
كلاوسيت، نيومان، ومور	.38/0s	0.772/3.6 ثانية	0.692/799 ثانية	0.927/5034 ثانية	-/-	-/-	-/-
بونس ولاتابي	.42/0s	0.757/3.3 ثانية	0.729/575 ثانية	0.895/6666 ثانية	-/-	-/-	-/-
واكيتا وتسورومي	.42/0s	0.761/0.7 ثانية	0.667/62 ثانية	0.898/248 ثانية	0.56/464 ثانية	-/-	-/-
طريقة لوفان	.42/0s	0.813/0s	0.781/1 ثانية	0.935/3 ثانية	0.769/134 ثانية	0.979/738 ثانية	0.984/152mn

يشير الرمز -/- في الجدول إلى طريقة استغرقت أكثر من 24 ساعة لتنفيذها. يوضح هذا الجدول (من ^{[ 1 ]}^{و[ 17 ]} ) أن طريقة لوفان تتفوق على العديد من طرق تحسين النمطية المماثلة في كلٍ من النمطية والوقت.

انظر أيضاً

مراجع

1 2 3 4 5 بلونديل، فنسنت د؛ غيوم، جان لوب؛ لامبيوت، رينو؛ لوفيفر، إتيان (9 أكتوبر 2008). "التطور السريع للمجتمعات في الشبكات الكبيرة". مجلة الميكانيكا الإحصائية: النظرية والتجربة . 2008 (10) 10008. arXiv : 0803.0476 . Bibcode : 2008JSMTE..10..008B . doi : 10.1088/1742-5468/2008/10/P10008 . S2CID 334423 .
1 2 كلاوسيت، آرون؛ نيومان، إم إي جيه؛ مور، كريستوفر (2004-12-06). "إيجاد بنية المجتمع في الشبكات الكبيرة جدًا". مجلة Physical Review E. 70 ( 6) 066111. arXiv : cond-mat/0408187 . Bibcode : 2004PhRvE..70f6111C . doi : 10.1103/PhysRevE.70.066111 . ISSN 1539-3755 . PMID 15697438. S2CID 8977721 .
↑ كوهين-أداد، فينسنت؛ كوسوفسكي، أدريان؛ مالمان-ترين، فريدريك؛ سولبيك، ديفيد (2020). "حول قوة لوفان في نموذج الكتلة العشوائية". التطورات في أنظمة معالجة المعلومات العصبية (Neurips 2020) . كوران أسوشيتس، ص 4055-4066 .
↑ غيميرا، روجر؛ ساليس-باردو، مارتا؛ أمارال، لويس أ. نونيس (19 أغسطس 2004). "النمطية من التقلبات في الرسوم البيانية العشوائية والشبكات المعقدة" . مجلة Physical Review E. 70 ( 2) 025101. doi : 10.1103/PhysRevE.70.025101 . PMC 2441765. تاريخ الاسترجاع: 8 أكتوبر 2013 .
↑ قاسمييان، أمير؛ حسينمردي، هما؛ كلاوسيت، آرون (2019). "تقييم التجاوز والنقص في نماذج بنية مجتمع الشبكة". معاملات IEEE في هندسة المعرفة والبيانات : 1-1 . arXiv : 1802.10582 . doi : 10.1109/TKDE.2019.2911585 . ISSN 2326-3865 .
↑ بيكسوتو، تياغو ب.؛ كيركلي، أليك (23 أغسطس 2023). "النماذج الضمنية، والضغط الكامن، والتحيزات الجوهرية، والحلول السريعة في اكتشاف المجتمعات" . مجلة Physical Review E. 108 ( 2) 024309. الجمعية الفيزيائية الأمريكية. doi : 10.1103/PhysRevE.108.024309 . تاريخ الاسترجاع: 18 مارس 2024 .
^ غوش، سايان؛ هالابانافار، ماهانتيش؛ توميو، أنتونينو؛ كاليانارامان، أنانث؛ لو، هاو؛ تشافاريا ميراندا، دانيال ج.؛ خان، عارف؛ جبرمدهين، أسفاو حديش (2018). “خوارزمية لوفان الموزعة للكشف عن مجتمع الرسم البياني” (PDF) . ندوة IEEE الدولية للمعالجة المتوازية والموزعة لعام 2018، IPDPS 2018، فانكوفر، كولومبيا البريطانية، كندا، 21-25 مايو 2018 . جمعية IEEE للكمبيوتر. الصفحات من 885 إلى 895. دوى : 10.1109/IPDPS.2018.00098 . رقم ISBN 978-1-5386-4368-6.
1 2 3 4 تراغ، فيرجينيا؛ والتمان، L.؛ فان إيك، نيوجيرسي (2019-03-26). "من لوفان إلى ليدن: ضمان مجتمعات جيدة التواصل" . التقارير العلمية . 9 (1): 5233. أرخايف : 1810.08473 . بيب كود : 2019NatSR...9.5233T . دوى : 10.1038/s41598-019-41695-z . ISSN 2045-2322 . بمك 6435756 . بميد 30914743 .
↑ "طريقة لوفان للكشف عن المجتمعات" . perso.uclouvain.be . تم الاطلاع عليه بتاريخ 21-11-2024 .
↑ "لوفان - التحليلات والخوارزميات - Ultipa Graph" . www.ultipa.com . تاريخ الاسترجاع: 21-11-2024 .
↑ بوجول، جوزيب م.؛ إيراميلي، فيجاي؛ رودريغيز، بابلو (2009). "فرق تسد: تقسيم الشبكات الاجتماعية عبر الإنترنت". arXiv : 0905.4918v1 [ cs.NI ].
↑ غرين، ديريك؛ دويل، دونال؛ كانينغهام، بادريغ (مايو 2011). تتبع تطور المجتمعات في الشبكات الاجتماعية الديناميكية (ملف PDF) (تقرير فني). جامعة دبلن. UCD-CSI-2011-06. مؤرشف من الأصل (ملف PDF) بتاريخ 12 مايو 2013. تم الاطلاع عليه بتاريخ 20 نوفمبر 2014 .
↑ ماركوفيتش، عمر؛ كراسنوغور، ناتاليو (2018). " التنبؤ بظهور الأنواع في شبكات ما قبل الحياة المعقدة المحاكاة" . PLOS ONE . 13 (2) e0192871. Bibcode : 2018PLoSO..1392871M . doi : 10.1371/journal.pone.0192871 . PMC 5813963. PMID 29447212 .
↑ بونس، باسكال؛ لاتابي، ماثيو (2006). "حساب المجتمعات في الشبكات الكبيرة باستخدام المسارات العشوائية" (ملف PDF) . مجلة خوارزميات وتطبيقات الرسوم البيانية . 10 (2): 191-218 . arXiv : cond-mat/0412368 . doi : 10.7155/jgaa.00124 . S2CID 121714719 .
↑ واكيتا، كين؛ تسورومي، توشيوكي (2007). "إيجاد بنية المجتمع في الشبكات الاجتماعية واسعة النطاق". arXiv : cs/0702048 .
↑ بلونديل، فنسنت د.؛ غيوم، جان لوب؛ لامبيوت، رينو؛ لوفيفر، إتيان (2008). "التطور السريع للمجتمعات في الشبكات الكبيرة". مجلة الميكانيكا الإحصائية: النظرية والتجربة . 2008 (10) 10008. arXiv : 0803.0476 . Bibcode : 2008JSMTE..10..008B . doi : 10.1088/1742-5468/2008/10/P10008 . S2CID 334423 .
↑ أينو، توماس؛ بلونديل، فنسنت د.؛ غيوم، جان لوب؛ لامبيوت، رينو (2013). "التحسين المحلي متعدد المستويات للنمطية" . في: بيشو، تشارلز إدموند؛ سياري، باتريك (محرران). تقسيم الرسوم البيانية ( الطبعة الأولى). وايلي (نُشر في 13 فبراير 2013). الصفحات 315-345 . doi : 10.1002/9781118601181.ch13 . ISBN 978-1-84821-233-6.

"طريقة لوفان لاكتشاف المجتمعات في الشبكات الكبيرة" - فنسنت بلونديل http://perso.uclouvain.be/vincent.blondel/research/louvain.html

[Louvain-1] 1 2 3 4 5 بلونديل، فنسنت د؛ غيوم، جان لوب؛ لامبيوت، رينو؛ لوفيفر، إتيان (9 أكتوبر 2008). "التطور السريع للمجتمعات في الشبكات الكبيرة". مجلة الميكانيكا الإحصائية: النظرية والتجربة . 2008 (10) 10008. arXiv : 0803.0476 . Bibcode : 2008JSMTE..10..008B . doi : 10.1088/1742-5468/2008/10/P10008 . S2CID 334423 .

[Clauset-2] 1 2 كلاوسيت، آرون؛ نيومان، إم إي جيه؛ مور، كريستوفر (2004-12-06). "إيجاد بنية المجتمع في الشبكات الكبيرة جدًا". مجلة Physical Review E. 70 ( 6) 066111. arXiv : cond-mat/0408187 . Bibcode : 2004PhRvE..70f6111C . doi : 10.1103/PhysRevE.70.066111 . ISSN 1539-3755 . PMID 15697438. S2CID 8977721 .

[Cohen-Addad-3] كوهين-أداد، فينسنت؛ كوسوفسكي، أدريان؛ مالمان-ترين، فريدريك؛ سولبيك، ديفيد (2020). "حول قوة لوفان في نموذج الكتلة العشوائية". التطورات في أنظمة معالجة المعلومات العصبية (Neurips 2020) . كوران أسوشيتس، ص 4055-4066 .

[4] غيميرا، روجر؛ ساليس-باردو، مارتا؛ أمارال، لويس أ. نونيس (19 أغسطس 2004). "النمطية من التقلبات في الرسوم البيانية العشوائية والشبكات المعقدة" . مجلة Physical Review E. 70 ( 2) 025101. doi : 10.1103/PhysRevE.70.025101 . PMC 2441765. تاريخ الاسترجاع: 8 أكتوبر 2013 .

[5] قاسمييان، أمير؛ حسينمردي، هما؛ كلاوسيت، آرون (2019). "تقييم التجاوز والنقص في نماذج بنية مجتمع الشبكة". معاملات IEEE في هندسة المعرفة والبيانات : 1-1 . arXiv : 1802.10582 . doi : 10.1109/TKDE.2019.2911585 . ISSN 2326-3865 .

[6] بيكسوتو، تياغو ب.؛ كيركلي، أليك (23 أغسطس 2023). "النماذج الضمنية، والضغط الكامن، والتحيزات الجوهرية، والحلول السريعة في اكتشاف المجتمعات" . مجلة Physical Review E. 108 ( 2) 024309. الجمعية الفيزيائية الأمريكية. doi : 10.1103/PhysRevE.108.024309 . تاريخ الاسترجاع: 18 مارس 2024 .

[7] غوش، سايان؛ هالابانافار، ماهانتيش؛ توميو، أنتونينو؛ كاليانارامان، أنانث؛ لو، هاو؛ تشافاريا ميراندا، دانيال ج.؛ خان، عارف؛ جبرمدهين، أسفاو حديش (2018). “خوارزمية لوفان الموزعة للكشف عن مجتمع الرسم البياني” (PDF) . ندوة IEEE الدولية للمعالجة المتوازية والموزعة لعام 2018، IPDPS 2018، فانكوفر، كولومبيا البريطانية، كندا، 21-25 مايو 2018 . جمعية IEEE للكمبيوتر. الصفحات من 885 إلى 895. دوى : 10.1109/IPDPS.2018.00098 . رقم ISBN 978-1-5386-4368-6.

[:0-8] 1 2 3 4 تراغ، فيرجينيا؛ والتمان، L.؛ فان إيك، نيوجيرسي (2019-03-26). "من لوفان إلى ليدن: ضمان مجتمعات جيدة التواصل" . التقارير العلمية . 9 (1): 5233. أرخايف : 1810.08473 . بيب كود : 2019NatSR...9.5233T . دوى : 10.1038/s41598-019-41695-z . ISSN 2045-2322 . بمك 6435756 . بميد 30914743 .

[9] "طريقة لوفان للكشف عن المجتمعات" . perso.uclouvain.be . تم الاطلاع عليه بتاريخ 21-11-2024 .

[10] "لوفان - التحليلات والخوارزميات - Ultipa Graph" . www.ultipa.com . تاريخ الاسترجاع: 21-11-2024 .

[11] بوجول، جوزيب م.؛ إيراميلي، فيجاي؛ رودريغيز، بابلو (2009). "فرق تسد: تقسيم الشبكات الاجتماعية عبر الإنترنت". arXiv : 0905.4918v1 [ cs.NI ].

[12] غرين، ديريك؛ دويل، دونال؛ كانينغهام، بادريغ (مايو 2011). تتبع تطور المجتمعات في الشبكات الاجتماعية الديناميكية (ملف PDF) (تقرير فني). جامعة دبلن. UCD-CSI-2011-06. مؤرشف من الأصل (ملف PDF) بتاريخ 12 مايو 2013. تم الاطلاع عليه بتاريخ 20 نوفمبر 2014 .

[13] ماركوفيتش، عمر؛ كراسنوغور، ناتاليو (2018). " التنبؤ بظهور الأنواع في شبكات ما قبل الحياة المعقدة المحاكاة" . PLOS ONE . 13 (2) e0192871. Bibcode : 2018PLoSO..1392871M . doi : 10.1371/journal.pone.0192871 . PMC 5813963. PMID 29447212 .

[14] بونس، باسكال؛ لاتابي، ماثيو (2006). "حساب المجتمعات في الشبكات الكبيرة باستخدام المسارات العشوائية" (ملف PDF) . مجلة خوارزميات وتطبيقات الرسوم البيانية . 10 (2): 191-218 . arXiv : cond-mat/0412368 . doi : 10.7155/jgaa.00124 . S2CID 121714719 .

[15] واكيتا، كين؛ تسورومي، توشيوكي (2007). "إيجاد بنية المجتمع في الشبكات الاجتماعية واسعة النطاق". arXiv : cs/0702048 .

[16] بلونديل، فنسنت د.؛ غيوم، جان لوب؛ لامبيوت، رينو؛ لوفيفر، إتيان (2008). "التطور السريع للمجتمعات في الشبكات الكبيرة". مجلة الميكانيكا الإحصائية: النظرية والتجربة . 2008 (10) 10008. arXiv : 0803.0476 . Bibcode : 2008JSMTE..10..008B . doi : 10.1088/1742-5468/2008/10/P10008 . S2CID 334423 .

[17] أينو، توماس؛ بلونديل، فنسنت د.؛ غيوم، جان لوب؛ لامبيوت، رينو (2013). "التحسين المحلي متعدد المستويات للنمطية" . في: بيشو، تشارلز إدموند؛ سياري، باتريك (محرران). تقسيم الرسوم البيانية ( الطبعة الأولى). وايلي (نُشر في 13 فبراير 2013). الصفحات 315-345 . doi : 10.1002/9781118601181.ch13 . ISBN 978-1-84821-233-6.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ] .

[ 16 ]

و[ 17 ]