نقشه راه GIS

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

کاربرد جی ای اس

 

خلاصه

:

گره های تاثیرگذار در شبکه های اجتماعی نادر هستند، اما نفوذ آنها می تواند به سرعت به اکثر گره های شبکه سرایت کند. شناسایی گره های تاثیرگذار به ما امکان می دهد تا شیوع بیماری های همه گیر را بهتر کنترل کنیم، انتشار اطلاعات را تسریع کنیم، تبلیغات تجارت الکترونیکی موفق انجام دهیم و غیره. روش‌های کلاسیک برای رتبه‌بندی گره‌های تأثیرگذار محدودیت‌هایی دارند، زیرا تأثیر توپولوژی گره‌های همسایه را بر روی یک گره نادیده می‌گیرند. برای حل این مشکل، یک معیار جدید مبتنی بر مرکزیت محلی با یک ضریب پیشنهاد می‌کنیم. الگوریتم پیشنهادی هم اتصالات توپولوژیکی بین همسایگان و هم تعداد گره های همسایه را در نظر می گیرد. ابتدا، تعداد گره‌های همسایه را محاسبه می‌کنیم تا گره‌ها را در مراکز خوشه‌ای و آن‌هایی که ویژگی «bridge» را نشان می‌دهند شناسایی کنیم. سپس، ما یک تابع کاهشی برای ضریب خوشه‌بندی محلی گره‌ها می‌سازیم که ضریب مرکزیت محلی نامیده می‌شود، که گره‌هایی را که تعداد همسایه‌های چهار لایه یکسانی دارند، رتبه‌بندی می‌کند. ما آزمایش‌هایی را برای اندازه‌گیری تأثیر گره بر روی شبکه‌های واقعی و رایانه‌ای با استفاده از شش معیار انجام می‌دهیم: مرکزیت درجه، مرکزیت بین، مرکزیت نزدیک، K-Shell، مرکزیت نیمه محلی و اندازه گیری ما. نتایج نشان می‌دهد که رتبه‌بندی‌های به‌دست‌آمده توسط معیار پیشنهادی شبیه‌ترین رتبه‌بندی‌های مدل معیار حساس-آلوده-بازیابی شده است، بنابراین تأیید می‌کند که اندازه‌گیری ما با دقت بیشتری تأثیر گره‌ها را نسبت به سایر اقدامات منعکس می‌کند. علاوه بر این، در میان شش معیار آزمایش شده، روش ما تأثیر گره را به طور مؤثر متمایز می کند. که گره هایی را که تعداد همسایه های چهار لایه یکسانی دارند، رتبه بندی می کند. ما آزمایش‌هایی را برای اندازه‌گیری تأثیر گره بر روی شبکه‌های واقعی و رایانه‌ای با استفاده از شش معیار انجام می‌دهیم: مرکزیت درجه، مرکزیت بین، مرکزیت نزدیک، K-Shell، مرکزیت نیمه محلی و اندازه گیری ما. نتایج نشان می‌دهد که رتبه‌بندی‌های به‌دست‌آمده توسط معیار پیشنهادی شبیه‌ترین رتبه‌بندی‌های مدل معیار حساس-آلوده-بازیابی شده است، بنابراین تأیید می‌کند که اندازه‌گیری ما با دقت بیشتری تأثیر گره‌ها را نسبت به سایر اقدامات منعکس می‌کند. علاوه بر این، در میان شش معیار آزمایش شده، روش ما تأثیر گره را به طور مؤثر متمایز می کند. که گره هایی را که تعداد همسایه های چهار لایه یکسانی دارند، رتبه بندی می کند. ما آزمایش‌هایی را برای اندازه‌گیری تأثیر گره بر روی شبکه‌های واقعی و رایانه‌ای با استفاده از شش معیار انجام می‌دهیم: مرکزیت درجه، مرکزیت بین، مرکزیت نزدیک، K-Shell، مرکزیت نیمه محلی و اندازه گیری ما. نتایج نشان می‌دهد که رتبه‌بندی‌های به‌دست‌آمده توسط معیار پیشنهادی شبیه‌ترین رتبه‌بندی‌های مدل معیار حساس-آلوده-بازیابی شده است، بنابراین تأیید می‌کند که اندازه‌گیری ما با دقت بیشتری تأثیر گره‌ها را نسبت به سایر اقدامات منعکس می‌کند. علاوه بر این، در میان شش معیار آزمایش شده، روش ما تأثیر گره را به طور مؤثر متمایز می کند. مرکزیت درجه، مرکزیت بین، مرکزیت نزدیک، K-Shell، مرکزیت نیمه محلی و معیار ما. نتایج نشان می‌دهد که رتبه‌بندی‌های به‌دست‌آمده توسط معیار پیشنهادی شبیه‌ترین رتبه‌بندی‌های مدل معیار حساس-آلوده-بازیابی شده است، بنابراین تأیید می‌کند که اندازه‌گیری ما با دقت بیشتری تأثیر گره‌ها را نسبت به سایر اقدامات منعکس می‌کند. علاوه بر این، در میان شش معیار آزمایش شده، روش ما تأثیر گره را به طور مؤثر متمایز می کند. مرکزیت درجه، مرکزیت بین، مرکزیت نزدیک، K-Shell، مرکزیت نیمه محلی و معیار ما. نتایج نشان می‌دهد که رتبه‌بندی‌های به‌دست‌آمده توسط معیار پیشنهادی شبیه‌ترین رتبه‌بندی‌های مدل معیار حساس-آلوده-بازیابی شده است، بنابراین تأیید می‌کند که اندازه‌گیری ما با دقت بیشتری تأثیر گره‌ها را نسبت به سایر اقدامات منعکس می‌کند. علاوه بر این، در میان شش معیار آزمایش شده، روش ما تأثیر گره را به طور مؤثر متمایز می کند.
کلید واژه ها: 

شبکه های اجتماعی ؛ تأثیر گره ها ؛ مرکزیت محلی ؛ ضریب خوشه بندی

 

1. معرفی

شبکه های اجتماعی یک معماری انتشار اطلاعات توزیع شده جدید ایجاد کرده اند که توانایی مردم را برای انتشار و به دست آوردن اطلاعات بسیار بهبود می بخشد [ 1 ]. در معماری انتشار شبکه های اجتماعی، گسترش اطلاعات اغلب تحت تأثیر گره های خاص قرار می گیرد. نتایج تحقیقات نشان می‌دهد که این گره‌های بسیار تأثیرگذار در شبکه‌های اجتماعی نادر هستند، اما تأثیر آنها می‌تواند به سرعت به بیشتر گره‌های شبکه سرایت کند. این گره های حیاتی تا حد زیادی بر ساختار و عملکرد شبکه ها تأثیر می گذارند. شناسایی این گره های تاثیرگذار به درک بهتر شبکه های پیچیده کمک می کند. علاوه بر این، چنین شناسایی می تواند به پیش بینی دقیق و کنترل تکامل شبکه کمک کند.
در سال‌های اخیر، معیارهای مختلف مرکزی برای شناسایی گره‌های حیاتی پیشنهاد شده‌اند مانند مرکزیت درجه (DC) [ 2 ]، مرکزیت بین (BC) [ 3 ]، مرکزیت نزدیکی (CC) [ 4 ]، K-Shell (KS) [ 5 ] و غیره. بر اساس این معیارهای اساسی، محققان بسیاری از الگوریتم های نفوذ کاوی دیگر را پیشنهاد کرده اند [ 5 ، 6 ، 7 ، 8 ، 9 ، 10 ، 11 ، 12 ، 13 ، 14.]. مرکزیت درجه یک متریک ساده است و پیچیدگی محاسباتی کمی دارد. با این حال، نتیجه آن به اندازه کافی دقیق نیست زیرا فقط اطلاعات گره محلی را در نظر می گیرد. چن و همکاران [ 6 ] یک معیار مرکزیت نیمه محلی (LC) پیشنهاد کرد که هم نزدیکترین و هم نزدیکترین همسایه های یک گره را در نظر می گیرد. LC دقت را به قیمت پیچیدگی محاسباتی کم بهبود می بخشد. BC و CC تأثیر گره‌ها را بر اساس ساختار جهانی محاسبه می‌کنند و به دقت بالاتری دست می‌یابند. با این حال، آنها قادر به اعمال در شبکه های مقیاس بزرگ نیستند زیرا آنها نیاز به محاسبه کوتاه ترین مسیرها بین تمام جفت گره ها در شبکه دارند، که بسیار وقت گیر است [ 3 ، 4 ، 8 ]. کیتساک و همکاران [ 5] اشاره کرد که تأثیرگذارترین پخش کننده ها با گره هایی با بیشترین درجه مطابقت ندارند، بلکه با گره هایی که در هسته شبکه قرار دارند، مطابق با تجزیه K-Shell هستند. با این حال، روش K-Shell می تواند تأثیرات گره ها را تنها به چند سطح تقسیم کند: تجزیه و تحلیل آن درشت است، و بنابراین، معمولاً تنها برای شناسایی تأثیرگذارترین گره ها در شبکه استفاده می شود. لیو و همکاران [ 9 ] کشف کرد که همه شبکه های واقعی از قوانینی پیروی نمی کنند که گره ها در پوسته های بالا بسیار تأثیرگذار هستند. در برخی از شبکه‌ها، گره‌ها در پوسته‌های بالا، حتی آن‌هایی که در درونی‌ترین هسته قرار دارند، پخش‌کننده خوبی نیستند: Lie et al. اینها را یک گروه هسته مانند نامیدند. بر اساس نتایج فوق، آنها معیار دقیق تری K-Shell را پیشنهاد کردند که گره های تأثیرگذار را با حذف لبه های بین گره های هسته مانند شناسایی می کند.10 ]; با این حال، این روش هنوز تاثیر اتصالات توپولوژیکی بین گره های همسایه را در نظر نمی گیرد.
مطالعات نشان می دهد که تنوع اتصالات توپولوژیکی بین همسایگان تأثیر قابل توجهی بر تأثیر گره دارد. گره هایی با درجه یکسان می توانند تأثیراتی داشته باشند که با تعداد مؤلفه های متصل همسایگانشان نسبت معکوس دارد [ 11 , 12 , 13 , 14 , 15]. علاوه بر این، رشد انفجاری شبکه های اجتماعی به کارایی اقدامات نفوذ اهمیت می دهد. بنابراین، در شبکه‌های اجتماعی در مقیاس بزرگ، برای شناسایی کارآمد و دقیق گره‌های حیاتی، باید هم مرکزیت یک گره و هم ارتباطات توپولوژیکی بین همسایگان آن در نظر گرفته شود. ضریب خوشه بندی محلی یک معیار مهم است که تراکم تعاملات بین همسایگان را نشان می دهد [ 8 و 16]]. بنابراین، ما یک معیار جدید مبتنی بر مرکزیت محلی با یک ضریب (CLC) پیشنهاد می‌کنیم که در آن ضریب خوشه‌بندی محلی یک گره برای اندازه‌گیری تأثیر آن علاوه بر مرکزیت نیمه محلی آن استفاده می‌شود. ما آزمایش‌هایی را برای اندازه‌گیری تأثیر گره با استفاده از DC، BC، CC، KS، LC و CLC انجام دادیم. نتایج نشان می‌دهد که دقت CLC مشابه یا بهتر از پنج معیار دیگر مرکزی است، با این حال افزایش کمی در هزینه زمان دارد.
بقیه این مقاله به شرح زیر سازماندهی شده است. بخش 2 معیار پیشنهادی جدید، CLC را معرفی می کند. در بخش 3 ، ما هشت مجموعه داده و روش‌های ارزیابی مورد استفاده برای مطالعه دقیق‌ترین معیارها را معرفی می‌کنیم. ما همچنین نتایج تجربی را در این بخش تجزیه و تحلیل می کنیم. بخش 4 مقاله را به پایان می رساند و کارهای احتمالی آینده را فهرست می کند.

2. مرکزیت محلی با ضریب اندازه گیری تأثیر گره

ما در این مقاله بر روی شبکه های بی وزن، بدون جهت و ساده تمرکز می کنیم. اجازه دهید V، ای)G=(�,�)یک نمودار با V|n=|�|رئوس و E|m=|�|لبه ها. تاثیر گره vبا نشان داده می شود سیC)���(�):

سیCf× C،���(�)=�(�(�))×��(�)،

جایی که C)��(�)معیار مرکزیت نیمه محلی است، ج )ج()ضریب خوشه بندی محلی گره v است و fج ) )(ج())اثر ضریب خوشه بندی v را به حساب می آورد :

C=∈ Γ )) ،سی()=تو()س(تو)،
=∈ Γ )ن) ،س(تو)=(تو)ن()،

جایی که Γ )()مجموعه نزدیکترین همسایگان گره v است و )ن()تعداد نزدیکترین و نزدیکترین همسایگان گره w است . معمولاً ضریب خوشه بندی محلی ( ج )ج()) در حین انتشار نقش منفی دارد [ 13 , 14 , 15 ]; بدین ترتیب، fج ) )(ج())نشان دهنده تابع کاهشی است ج )ج():

fج =ه− ).(ج())=هج().
ما ابتدا کارایی روش خود را با بررسی پیچیدگی محاسباتی آن نشان می دهیم. در حال محاسبه )ن()نیاز به عبور از همسایگی گره w در دو مرحله دارد که هزینه دارد ای (⟨ 2)O(ک2)، جایی که ⟨ کمیانگین درجه شبکه است. پیچیدگی محاسباتی برای محاسبه ضریب خوشه بندی محلی هر گره O( n ). بنابراین، پیچیدگی محاسباتی کل برای معیار مرکزیت ما است n⟨ 2)O(ک2)که همان اندازه گیری LC است و پیچیدگی محاسباتی بسیار کمتری نسبت به اندازه گیری BC یا CC دارد. علاوه بر این، در جدول 1 ، زمان CPU (واحد پردازش مرکزی، Core i5-6300 2.4 گیگاهرتز) را برای شش معیار مرکزی در پنج شبکه واقعی که در بخش 3.1 شرح داده شده است نشان می‌دهیم : ایمیل، توییتر، فیس‌بوک، Epinions و بلاگ. می بینیم که اندازه گیری ما به زمان کمی بیشتر از LC اما زمان بسیار کمتری نسبت به BC، CC و KS نیاز دارد، به خصوص در شبکه های مقیاس بزرگ. در مقایسه با LC، زمان اجرای CLC کمتر از 0.5 ثانیه افزایش می یابد و نرخ رشد آن کمتر از 2٪ در هر پنج شبکه واقعی است.
اندازه گیری CLC هم اتصالات توپولوژیکی بین گره های همسایه و هم تعداد گره های همسایه را در نظر می گیرد. گره های حیاتی در شبکه ها معمولاً آنهایی هستند که در هسته یک خوشه گره قرار دارند یا به عنوان پل بین خوشه های گره عمل می کنند. برای اطمینان از پیچیدگی محاسباتی کم، ناحیه محلی یک گره فقط شامل همسایگان چهار لایه آن است. برای هر گره در شبکه، هر چه تعداد گره ها در ناحیه محلی آن بیشتر باشد، آن گره حیاتی تر است. به این ترتیب، می‌توان گره‌هایی را که در هسته خوشه‌های گره قرار دارند و آن دسته از گره‌های درجه پایین را که به عنوان پل بین خوشه‌های گره عمل می‌کنند، شناسایی کرد. همانطور که در شکل 1 نشان داده شده است، گره 2 در هسته یک خوشه گره قرار دارد و گره 3 یک گره پل است. اگرچه درجات گره های 2 و 3 از درجه گره 1 کوچکتر است، اما گره های اول دارای همسایگان چهار لایه زیادی هستند. بنابراین ما آنها را نیز دارای نفوذ بالایی می دانیم. برای رتبه بندی گره هایی با تعداد همسایه های چهار لایه یکسان، ضریب خوشه بندی گره محلی را محاسبه کرده و یک تابع کاهشی از آن می سازیم. هر چه ضریب خوشه بندی محلی یک گره بزرگتر باشد، گره های همسایه آن به جای گره های دیگر، محکم تر به یکدیگر متصل می شوند، که انتشار اطلاعات آغاز شده از گره را در یک منطقه محلی محدود می کند و تأثیر گره ها را ضعیف می کند. به طور خلاصه،

3. نتایج تجربی

3.1. مجموعه داده های مورد استفاده در آزمایش ها

برای ارزیابی اثربخشی و کارایی معیار مرکزی پیشنهادی ما، آن را برای شبکه‌های واقعی و مصنوعی اعمال می‌کنیم. شبکه های واقعی شامل ایمیل [ 17 ]، توییتر [ 18 ]، فیس بوک [ 19 ]، Epinions [ 20 ] و بلاگ [ 21 ] هستند که همگی به عنوان هدایت نشده در نظر گرفته می شوند. شبکه های مصنوعی شامل شبکه های تولید شده توسط مدل شبکه تصادفی Erdos-Renyi (ER) [ 8 ]، مدل شبکه Watts-Strogatz (WS) [ 8 ] و مدل شبکه بدون مقیاس Barabási-Albert (BA) [ 8 ]، می باشد. و همگی بی جهت و بی وزن هستند. ویژگی های توپولوژیکی اصلی هشت شبکه در جدول 2 خلاصه شده است. n و m به ترتیب تعداد کل گره ها و پیوندها هستند. ⟨ کو کxکمترآایکسمیانگین و حداکثر درجه را به ترتیب نشان دهید، C ضریب خوشه بندی است و βتی ساعتتیساعتآستانه اپیدمی است. در شبکه های همگن مانند ER و WS، βتی ساعت=1⟨ تیساعت=1ک، در حالی که در شبکه های ناهمگن، βتی ساعت=⟨ ک2تیساعت=کک28 ، 22 ].

3.2. روشهای ارزیابی

ما لیست های رتبه بندی شده را با اعمال شش معیار در هر شبکه به دست آوردیم. در اصل، فهرست رتبه‌بندی‌شده ایجاد شده توسط یک روش رتبه‌بندی مؤثر باید تا حد امکان با فهرست رتبه‌بندی تولید شده توسط فرآیند پخش واقعی سازگار باشد. برای شبیه‌سازی یک فرآیند انتشار واقعی و به دست آوردن تأثیر انتشار واقعی گره‌ها، مدل حساس-عفونی-بازیابی شده (SIR) [ 23 ] را اتخاذ کردیم. مدل SIR که معمولاً به عنوان معیاری برای اندازه‌گیری دقت سایر معیارهای تأثیر در نظر گرفته می‌شود، می‌تواند به طور مؤثر یک بیماری همه‌گیر و انتشار اطلاعات را شبیه‌سازی کند.
در مدل SIR، یک گره دارای سه حالت است: (1) حساس – یک گره قبل از اینکه توسط همسایگانش آلوده شود، در حالت حساس است. (2) گره آلوده شده که تازه آلوده شده است در این حالت است و می تواند همسایگان خود را با احتمالی آلوده کند. و (3) مقاوم – گرهی که در حال بهبودی بوده و نسبت به بیماری مصون است در این حالت قرار دارد.
در مدل SIR، تمام گره ها در ابتدا در حالت حساس هستند به جز یک گره، v که در حالت آلوده است. در هر مرحله زمانی، گره های آلوده همسایه های حساس خود را با احتمال β آلوده می کنند و با احتمال 1 وارد حالت بازیابی می شوند و پس از آن ایمن می شوند و نمی توانند دوباره آلوده شوند. فرآیند انتشار زمانی پایان می یابد که هیچ گره آلوده ای در شبکه وجود نداشته باشد. توانایی گسترش گره اصلی v ، اسβ)اس()، به عنوان تعداد گره هایی تعریف می شود که در پایان فرآیند انتشار که از گره v سرچشمه می گیرد آلوده شده اند . هنگامی که به β مقدار زیادی اختصاص داده می شود، فرآیند پخش خیلی سریع تمام می شود تا تأثیر گره را تشخیص دهد. بنابراین، ما مقدار کمی را به β اختصاص دادیم که تقریباً آستانه اپیدمی بود βتی ساعتتیساعت. ما تعداد شبیه‌سازی‌ها را 5000 تنظیم می‌کنیم. تأثیر گسترش یک گره به عنوان میانگین توانایی پخش گره v در کل محدوده β تعریف می‌شود . اسβ)¯¯¯¯¯¯¯¯¯اس()¯. مقدار β استفاده شده برای هر شبکه در جدول 3 آمده است .
ما می‌توانیم فهرستی از گره‌های رتبه‌بندی شده را با معیار خاصی به دست آوریم. برای ارزیابی درستی آن اندازه گیری، ما لیست را با لیست رتبه بندی تولید شده توسط مقایسه کردیم اسβ)¯¯¯¯¯¯¯¯¯اس()¯. هرچه همبستگی بین آنها بیشتر باشد، متریک دقیق تر است. ما تاو کندال را قبول می کنیم ( τ) به عنوان ضریب همبستگی رتبه ای [ 24 ]. تاو کندال ( τ) به صورت زیر تعریف می شود:

τ(آر1،آر2) =نجند12نن− 1 )(آر1،آر2)=نجند12ن(ن1)

جایی که آر1آر1و آر2آر2دو لیست رتبه بندی شده هستند که به ترتیب حاوی N عنصر هستند. هر جفت رتبه (آرi،آرمن)(آر1من،آر2من)و (آرj،آرj)(آر1،آر2)اگر رده‌های هر دو عنصر موافق باشند، می‌گویند: یعنی اگر هر دو آرi>آرjآر1من>آر1و آرمن>آرjآر2من>آر2یا اگر آرi<آرjآر1من<آر1و آرمن<آرjآر2من<آر2; در غیر این صورت، اگر آرi>آرjآر1من>آر1و آرمن<آرjآر2من<آر2یا اگر آرi<آرjآر1من<آر1و آرمن>آرjآر2من>آر2، گفته می شود که آنها ناسازگار هستند. اگر آرi=آرjآر1من=آر1یا آرمن=آرjآر2من=آر2، این جفت نه همخوان است و نه ناسازگار. نجنجو ندندبه ترتیب تعداد جفت های همخوان و ناسازگار را نشان دهید و τ∈ – ، 1 ]�∈[−1,1]. یک بالاتر τمقدار نشان می دهد که لیست رتبه بندی تولید شده توسط اندازه گیری دقیق تر است، و τ= 1 نشان می دهد که لیست رتبه بندی تولید شده توسط اندازه گیری دقیقاً مشابه لیست رتبه بندی شده توسط فرآیند پخش واقعی است.

3.3. نتایج تجربی و تجزیه و تحلیل

3.3.1. تاثیر رتبه گره ها

ما اثربخشی و کارایی اندازه گیری CLC را به صورت جداگانه در هر یک از هشت شبکه پیشنهادی در بخش 3.1 ارزیابی کردیم . برای شش شبکه اول، ما تأثیر گره‌ها را به ترتیب با استفاده از DC، BC، CC، KS، LC و CLC اندازه‌گیری کردیم. از آنجایی که KS برای شبکه های BA و WS اعمال نمی شود، ما عملکرد تنها پنج معیار دیگر را در آن دو شبکه آزمایش کردیم و نشان دادیم. ما محاسبه کردیم τمقادیر برای شش معیار تحت احتمالات انتشار مختلف β. نتایج در شکل 2 نشان می دهد که متریک CLC ما عملکرد بهتری را در طیف وسیعی از مقادیر احتمال انتشار به دست می آورد. β) برای هر هشت شبکه، که نشان دهنده استحکام معیار پیشنهادی است. به ویژه، زمانی که βنزدیک به آستانه اپیدمی است βتی ساعت��ℎ، τمقدار متریک CLC در تمام شبکه ها به جز شبکه ایمیل، بزرگترین است.
این τمقدار CLC از مقدار LC در شبکه ایمیل کوچکتر است زیرا ساختار جامعه در شبکه ایمیل به شدت خود مشابه است. در نتیجه، توپولوژی‌های گره‌های همسایه مشابه یکدیگر هستند [ 25 ] که توانایی تشخیص متریک CLC را کاهش می‌دهد. در شبکه BA، τمقدار CLC همان مقدار LC است وقتی βکوچک و برابر است βتی ساعت��ℎ. به عنوان βمقدار افزایش می یابد، CLC عملکرد کمی بدتر از LC دارد. ما استدلال می کنیم که این اتفاق می افتد زیرا ضریب خوشه بندی محلی شبکه BA که برای این مقاله ساخته ایم 0.011214 است. به عبارت دیگر، هیچ ویژگی خوشه‌بندی آشکاری ندارد. بنابراین، برای اکثر گره ها، شیب تابع fج ) )f(�(�))بزرگتر است و نسبت به ضریب خوشه بندی حساس تر است. تحت شرایط فوق، این بدان معنی است که گره های هم درجه که ساختارهای همسایگی آنها مشابه است، هنگام محاسبه توسط CLC تأثیرات متفاوتی خواهند داشت. بنابراین، می‌توان نتیجه گرفت که دقت متریک CLC کمی کمتر از LC در شبکه BA است. در شبکه بلاگ، CLC در کل محدوده کارآمدتر از LC است β، و بهترین عملکرد را زمانی به دست می آورد βنزدیک به آستانه اپیدمی است βتی ساعت��ℎ. با این حال، زمانی که βکمتر از 0.015 است، هر دو CLC و LC بدتر از DC و KS عمل می کنند. این نتیجه به این دلیل رخ می دهد که شبکه بلاگ ناهمگن است، به این معنی که گره های درجه بزرگ برای پیوند به گره های درجه کوچک مناسب هستند و بنابراین، روشی که تأثیر گره را با استفاده از تعداد همسایگان آن اندازه گیری می کند بهتر از روشی است که اندازه گیری می کند. نفوذ از طریق همسایگان چهار لایه. در پنج شبکه دیگر، CLC بهترین عملکرد را به دست می آورد. برای منعکس کردن توانایی پخش کلی همه گره ها، ما محاسبه می کنیم ⟨ τ〈�〉(مقدار متوسط ​​از τدر سراسر محدوده β). این ⟨ τ〈�〉مقادیر حاصل از تجزیه و تحلیل هشت شبکه با استفاده از معیارهای شش گانه در جدول 4 فهرست شده است . معیار CLC رتبه دوم را برای ایمیل ( ⟨ τسیC〈�〉���کوچکتر از ⟨ τC〈�〉��، سوم برای BA ( ⟨ τسیC〈�〉���کوچکتر از ⟨ τC〈�〉��و ⟨ τسیسی〈�〉��و سوم برای وبلاگ ( ⟨ τسیC〈�〉���کوچکتر از ⟨ τدی سی〈�〉��و ⟨ τکاس〈�〉��، اما در پنج شبکه دیگر، متریک CLC در رتبه اول قرار دارد. علاوه بر این، می‌توان مشاهده کرد که هیچ یک از روش‌ها به نتایج بهینه در تمام شبکه‌ها نمی‌رسند. در بین هشت شبکه، CLC در شش معیار رتبه برتر را کسب می کند و میانگین رتبه آن 1.625 است که از پنج معیار دیگر بهتر است و عملکرد آن پایدارترین است.

3.3.2. تاثیرگذارترین گره ها را رتبه بندی کنید

در بسیاری از کاربردهای عملی، مردم فقط به تأثیرگذارترین گره ها در شبکه علاقه مند هستند. تأثیرگذارترین گره ها آنهایی هستند که دارای قوی ترین میانگین توانایی پخش هستند اسβ)¯¯¯¯¯¯¯¯¯��(�)¯، که با میانگین گیری توانایی پخش گره در کل محدوده تخمین زده می شود βبا استفاده از شبیه سازی مدل SIR در این بخش، اندازه گیری دیگری را بررسی می کنیم، τL��، که فقط تاثیرگذارترین گره های Top- L را در نظر می گیرد، جایی که L از 20 تا 500 متغیر است. τL��دقیقاً مشابه محاسبه است τ. نتایج حاصل از پنج شبکه واقعی که با شش معیار در شکل 3 تجزیه و تحلیل شده اند نشان می دهد که CLC بهترین ها را به دست می آورد. τL��تقریباً در کل محدوده L در شبکه های ایمیل، توییتر و بلاگ ارزش دارد و بدیهی است که بهتر از LC است. در شبکه های Facebook و Epinions، CLC کمی بهتر از LC عمل می کند و بهترین امتیاز را کسب می کند. برای منعکس کردن دقت رتبه‌بندی گره‌های Top- L برای شش معیار، ما محاسبه کردیم τL〈��〉(مقدار متوسط ​​از τL��در کل محدوده L ). این τL〈��〉مقادیر حاصل از تجزیه و تحلیل پنج شبکه واقعی توسط شش معیار در جدول 5 فهرست شده است که نشان می دهد τLسیC〈��〉��سیبه دست آمده توسط CLC بزرگتر از پنج معیار دیگر مرکزیت در هر پنج شبکه واقعی است. در مقایسه با LC، τL〈��〉ارزش CLC به طور متوسط ​​9.50٪ افزایش می یابد. به طور کلی، متریک CLC در رتبه‌بندی مؤثرترین گره‌ها در شبکه‌ها بهتر از پنج معیار دیگر است.

3.3.3. قابلیت تشخیص قابلیت پخش گره ها

برای ارزیابی عملکرد اندازه گیری نفوذ یک گره، نه تنها باید دقت مرتب سازی و توانایی تشخیص گره های تأثیرگذار، بلکه قابلیت آن را برای تشخیص توانایی پخش گره ها نیز در نظر بگیریم. به عنوان مثال، K-Shell می تواند به طور موثر مؤثرترین گره ها را در یک شبکه شناسایی کند. با این حال، به دلیل اندازه درشت دانه آن، گره هایی با مقدار K-Shell یکسان را دارای تأثیر یکسان در نظر می گیرد. در نتیجه، τL��مقادیر به دست آمده توسط KS کوچکتر هستند، همانطور که در شکل 3 نشان داده شده است . برای اندازه‌گیری بیشتر اثربخشی معیارها، متریک تشخیص‌پذیری، D را تعریف کردیم تا اندازه‌گیری کنیم که معیارهای تأثیر گره چقدر می‌توانند توانایی گسترش گره را تشخیص دهند [ 26 ]:

=sتیدمن ffن،�=���������,

جایی که sتیدمن ff��������تعداد عناصر متمایز در یک لیست است که حاوی مقدار تمام گره های شبکه است که با یک اندازه گیری مشخص به دست می آید و N تعداد گره های شبکه است. حداکثر مقدار، 1�=1، نشان می دهد که به تمام گره های شبکه مقادیر متمایز اختصاص داده شده است و می توان آنها را به طور یکسان متمایز کرد، در حالی که مقدار حداقل، =1ن�=1�، نشان می دهد که به همه گره ها یک مقدار اختصاص داده شده است. بدیهی است که یک D بزرگتر نشان دهنده رتبه بندی دقیق گره ها است. نتایج D برای پنج شبکه واقعی در جدول 6 نشان داده شده است . اندازه گیری CLC بزرگترین مقادیر D را برای هر پنج شبکه به دست می آورد. از این رو، می توانیم نتیجه بگیریم که روش ما ریزدانه است و تأثیر گره را به طور مؤثرتری نسبت به پنج معیار دیگر متمایز می کند.

4. نتیجه گیری

در این مقاله، ما یک معیار جدید مبتنی بر مرکزیت محلی با یک ضریب (CLC) برای ارزیابی پخش‌کننده‌های تأثیرگذار در شبکه‌های اجتماعی پیشنهاد می‌کنیم. بر اساس یک اندازه گیری مرکزی نیمه محلی (LC)، روش ما اتصالات توپولوژیکی بین همسایگان و تعداد گره های همسایه را ترکیب می کند. علاوه بر این، از ضریب خوشه‌بندی محلی گره‌ها برای تشخیص تأثیر گره‌ها با همان تعداد همسایه‌های چهار لایه استفاده می‌کند، که بر محدودیت سایر معیارهای مرکزیت که تأثیر توپولوژی همسایه‌ها بر یک گره را نادیده می‌گیرند، غلبه می‌کند. در مقایسه با متریک LC، CLC فقط محاسبه ضریب خوشه بندی محلی گره ها را اضافه می کند. بنابراین، زمان محاسبه فقط اندکی افزایش می‌یابد و پیچیدگی و دقت محاسباتی را متعادل می‌کند. ما روش خود را برای شبکه‌های مصنوعی و واقعی اعمال کردیم و سه معیار را برای تأیید اثربخشی آن اتخاذ کردیم. نتایج تجربی نشان می‌دهد که اندازه‌گیری CLC بهتر از پنج روش دیگر آزمایش‌شده است و بهترین نتایج را برای رتبه‌بندی تأثیر گره‌ها، شناسایی پخش‌کننده‌های کلیدی و تمایز تأثیر گره‌ها به دست می‌آورد. علاوه بر این، روش ارائه شده در این مقاله را می توان به راحتی به شبکه های هدایت شده تعمیم داد. از آنجایی که مقیاس شبکه‌های اجتماعی همچنان در حال رشد است، طراحی روش‌های کارآمد و مؤثر برای رتبه‌بندی توانایی انتشار گره‌ها در شبکه‌های پیچیده یک چالش بلندمدت خواهد بود. بسیاری از شبکه های واقعی مانند شبکه جهانی وب شبکه های فراکتال هستند. انواع دیگر، مانند همکاری بازیگران و شبکه های سلولی، از الگوهای تکرار شونده خود تحت مقیاس های طول متفاوت تشکیل شده اند. نتایج تجربی نشان می‌دهد که اندازه‌گیری CLC بهتر از پنج روش دیگر آزمایش‌شده است و بهترین نتایج را برای رتبه‌بندی تأثیر گره‌ها، شناسایی پخش‌کننده‌های کلیدی و تمایز تأثیر گره‌ها به دست می‌آورد. علاوه بر این، روش ارائه شده در این مقاله را می توان به راحتی به شبکه های هدایت شده تعمیم داد. از آنجایی که مقیاس شبکه‌های اجتماعی همچنان در حال رشد است، طراحی روش‌های کارآمد و مؤثر برای رتبه‌بندی توانایی انتشار گره‌ها در شبکه‌های پیچیده یک چالش بلندمدت خواهد بود. بسیاری از شبکه های واقعی مانند شبکه جهانی وب شبکه های فراکتال هستند. انواع دیگر، مانند همکاری بازیگران و شبکه های سلولی، از الگوهای تکرار شونده خود تحت مقیاس های طول متفاوت تشکیل شده اند. نتایج تجربی نشان می‌دهد که اندازه‌گیری CLC بهتر از پنج روش دیگر آزمایش‌شده است و بهترین نتایج را برای رتبه‌بندی تأثیر گره‌ها، شناسایی پخش‌کننده‌های کلیدی و تمایز تأثیر گره‌ها به دست می‌آورد. علاوه بر این، روش ارائه شده در این مقاله را می توان به راحتی به شبکه های هدایت شده تعمیم داد. از آنجایی که مقیاس شبکه‌های اجتماعی همچنان در حال رشد است، طراحی روش‌های کارآمد و مؤثر برای رتبه‌بندی توانایی انتشار گره‌ها در شبکه‌های پیچیده یک چالش بلندمدت خواهد بود. بسیاری از شبکه های واقعی مانند شبکه جهانی وب شبکه های فراکتال هستند. انواع دیگر، مانند همکاری بازیگران و شبکه های سلولی، از الگوهای تکرار شونده خود تحت مقیاس های طول متفاوت تشکیل شده اند. و بهترین نتایج را برای رتبه بندی تأثیر گره ها، شناسایی پخش کننده های کلیدی و تشخیص تأثیر گره ها به دست می آورد. علاوه بر این، روش ارائه شده در این مقاله را می توان به راحتی به شبکه های هدایت شده تعمیم داد. از آنجایی که مقیاس شبکه‌های اجتماعی همچنان در حال رشد است، طراحی روش‌های کارآمد و مؤثر برای رتبه‌بندی توانایی انتشار گره‌ها در شبکه‌های پیچیده یک چالش بلندمدت خواهد بود. بسیاری از شبکه های واقعی مانند شبکه جهانی وب شبکه های فراکتال هستند. انواع دیگر، مانند همکاری بازیگران و شبکه های سلولی، از الگوهای تکرار شونده خود تحت مقیاس های طول متفاوت تشکیل شده اند. و بهترین نتایج را برای رتبه بندی تأثیر گره ها، شناسایی پخش کننده های کلیدی و تشخیص تأثیر گره ها به دست می آورد. علاوه بر این، روش ارائه شده در این مقاله را می توان به راحتی به شبکه های هدایت شده تعمیم داد. از آنجایی که مقیاس شبکه‌های اجتماعی همچنان در حال رشد است، طراحی روش‌های کارآمد و مؤثر برای رتبه‌بندی توانایی انتشار گره‌ها در شبکه‌های پیچیده یک چالش بلندمدت خواهد بود. بسیاری از شبکه های واقعی مانند شبکه جهانی وب شبکه های فراکتال هستند. انواع دیگر، مانند همکاری بازیگران و شبکه های سلولی، از الگوهای تکرار شونده خود تحت مقیاس های طول متفاوت تشکیل شده اند. طراحی روش‌های کارآمد و مؤثر برای رتبه‌بندی توانایی پخش گره‌ها در شبکه‌های پیچیده یک چالش بلندمدت خواهد بود. بسیاری از شبکه های واقعی مانند شبکه جهانی وب شبکه های فراکتال هستند. انواع دیگر، مانند همکاری بازیگران و شبکه های سلولی، از الگوهای تکرار شونده خود تحت مقیاس های طول متفاوت تشکیل شده اند. طراحی روش‌های کارآمد و مؤثر برای رتبه‌بندی توانایی پخش گره‌ها در شبکه‌های پیچیده یک چالش بلندمدت خواهد بود. بسیاری از شبکه های واقعی مانند شبکه جهانی وب شبکه های فراکتال هستند. انواع دیگر، مانند همکاری بازیگران و شبکه های سلولی، از الگوهای تکرار شونده خود تحت مقیاس های طول متفاوت تشکیل شده اند.27 ]. ویژگی اصلی یک شبکه فراکتال دافعه بین گره های هاب است که باعث می شود گره های هاب تمایل به عدم اتصال به سایر گره های هاب داشته باشند [ 28 ]. در اندازه گیری ما، برخی از گره های هاب به دلیل فاصله زیاد آنها در شبکه های فراکتال سهم کمی در تأثیر همسایگی هاب خود خواهند داشت و شباهت بین ماژول ها دقت اندازه گیری ما را کاهش می دهد. بنابراین، میزان عملکرد ما در شبکه‌های فراکتالی واقعی ممکن است به ابعاد فراکتالی آنها و فاصله بین ماژول‌های مشابه مرتبط باشد و جنبه‌ای است که هنوز به تحقیقات بیشتری نیاز دارد. علاوه بر این، تحقیقات بیشتر می‌تواند روابط اعتماد بین گره‌ها را برای تعیین اثرات آنها بر توانایی گسترش گره تجزیه و تحلیل کند.

منابع

  1. Mislove، شبکه های اجتماعی آنلاین AE: اندازه گیری، تجزیه و تحلیل و کاربردها در سیستم های اطلاعاتی توزیع شده. Ph.D. پایان نامه، دانشگاه رایس، هیوستون، تگزاس، ایالات متحده آمریکا، 2009. [ Google Scholar ]
  2. آلبرت، آر. جونگ، اچ. Barabasi, AL تحمل خطا و حمله شبکه های پیچیده. Nature 2000 , 406 , 542. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  3. فریمن، LC مجموعه ای از معیارهای مرکزیت مبتنی بر بین بودن. Sociometry 1977 ، 40 ، 35-41. [ Google Scholar ] [ CrossRef ]
  4. کراخارت، دی. ارزیابی چشم‌انداز سیاسی: ساختار، شناخت و قدرت در سازمان‌ها. دریاسالار علمی Q. 1990 , 35 , 342-369. [ Google Scholar ] [ CrossRef ]
  5. کیتساک، م. Gallos، LK; هاولین، اس. لیلجروس، اف. موچنیک، ال. یوجین استنلی، اچ. Makse، HA شناسایی پخش کننده های تأثیرگذار در شبکه های پیچیده. نات. فیزیک 2010 ، 6 ، 888-893. [ Google Scholar ] [ CrossRef ]
  6. رن، ایکس. لو، ال. Ren, X. بررسی گره های رتبه بندی در شبکه های پیچیده. چانه. J. 2014 ، 59 ، 1175-1188. [ Google Scholar ] [ CrossRef ]
  7. چن، دی. لو، ال. شانگ، ام اس؛ ژانگ، YC; Zhou، T. شناسایی گره های تاثیرگذار در شبکه های پیچیده. فیزیک یک آمار مکانیک. Appl. 2012 ، 391 ، 1777-1787. [ Google Scholar ] [ CrossRef ]
  8. وانگ، XF; لی، ایکس. Chen, GR اهمیت و شباهت گره ها. در علوم شبکه: مقدمه ; لیو، ی.، اد. انتشارات آموزش عالی: پکن، چین، 2012; صص 157-185. [ Google Scholar ]
  9. لیو، ی. تانگ، م. ژو، تی. آیا، Y. گروه های هسته مانند منجر به بی اعتباری شناسایی سوپر پخش کننده با تجزیه k-shell می شود. علمی Rep. 2015 , 5 , 9602–9609. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  10. لیو، ی. تانگ، م. ژو، تی. آیا، Y. بهبود دقت روش k-shell با حذف پیوندهای اضافی: از دیدگاه پویایی گسترش. علمی Rep. 2015 , 5 , 13172–13182. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  11. اوگاندر، جی. بکستروم، ال. مارلو، سی. کلینبرگ، J. تنوع ساختاری در سرایت اجتماعی. Proc. Natl. آکادمی علمی ایالات متحده آمریکا 2012 ، 109 ، 5962–5966. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  12. سو، XP؛ Song، YR از «حفره‌های ساختاری» همسایگی برای شناسایی پخش‌کننده‌های کلیدی در شبکه‌های اجتماعی استفاده می‌کند. Acta Phys. گناه چانه. اد. 2015 ، 64 ، 20101. [ Google Scholar ]
  13. اگویلوز، VM; Klemm, K. آستانه اپیدمی در شبکه های ساختاریافته بدون مقیاس. فیزیک کشیش لِت 2002 ، 89 ، 108701-108704. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  14. پیترمن، تی. de Los Rios، P. نقش خوشه‌بندی و نظم‌بندی شبکه‌ای در گسترش اپیدمی. فیزیک Rev. E Stat. فیزیک ماده نرم غیرخطی. 2004 ، 69 ، 279-307. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  15. ژو، تی. یان، جی. شبکه‌های مسطح Wang، BH حداکثر با ضریب خوشه‌بندی بزرگ و توزیع درجه قدرت-قانون. فیزیک Rev. E Stat. فیزیک ماده نرم غیرخطی. 2005 , 71 , 046141. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  16. واتس، دی جی؛ استروگاتز، SH دینامیک جمعی شبکه های جهان کوچک. طبیعت 1998 ، 393 ، 440-442. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  17. گویمرا، آر. دانون، ال. دیاز-گیلرا، آ. گیرالت، اف. Arenas، A. ساختار جامعه خود مشابه در شبکه ای از تعاملات انسانی. فیزیک Rev. E 2003 , 68 , 065103. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  18. مکولی، جی جی; Leskovec, J. یادگیری کشف حلقه های اجتماعی در شبکه های ego. Adv. عصبی Inf. روند. سیستم 2012 ، 25 ، 539-547. [ Google Scholar ]
  19. Traud، AL; موچا، پی جی؛ پورتر، کارشناسی ارشد ساختار اجتماعی شبکه های فیس بوک. فیزیک یک آمار مکانیک. Appl. 2011 ، 391 ، 4165-4180. [ Google Scholar ] [ CrossRef ]
  20. ریچاردسون، ام. آگراوال، آر. دومینگوس، پی. مدیریت اعتماد برای وب معنایی. لکت. یادداشت ها محاسبه. علمی 2003 ، 2870 ، 351-368. [ Google Scholar ]
  21. گرگوری، اس. یافتن جوامع همپوشانی با استفاده از الگوریتم‌های تشخیص جامعه غیرمجاز. شبکه مجتمع 2009 ، 207 ، 47-61. [ Google Scholar ]
  22. کاستلانو، سی. کشیش-ساتوراس، R. آستانه های شیوع بیماری همه گیر در شبکه ها. فیزیک کشیش لِت 2010 , 105 , 3305. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  23. Dorogovtsev، SN; Goltsev، AV; مندز، JFF پدیده های بحرانی در شبکه های پیچیده. Rev. Mod. فیزیک 2007 ، 80 ، 1275-1335. [ Google Scholar ] [ CrossRef ]
  24. کندال، ام جی اندازه گیری جدید همبستگی رتبه. Biometrika 1938 ، 30 ، 81-93. [ Google Scholar ] [ CrossRef ]
  25. لیو، ی. تانگ، م. ژو، تی. آیا، Y. شناسایی پخش کننده های تأثیرگذار در شبکه های پیچیده، نقش محله. فیزیک یک آمار مکانیک. Appl. 2016 ، 452 ، 289-298. [ Google Scholar ] [ CrossRef ]
  26. گائو، اس. ما، جی. چن، ز. وانگ، جی. Xing، CM رتبه بندی توانایی پخش گره ها در شبکه های پیچیده بر اساس ساختار محلی. فیزیک یک آمار مکانیک. Appl. 2014 ، 403 ، 130-147. [ Google Scholar ] [ CrossRef ]
  27. آهنگ، سی. هاولین، اس. Makse، HA خود شباهت شبکه های پیچیده. طبیعت 2005 ، 433 ، 392-395. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  28. آهنگ، سی. هاولین، اس. Makse، HA ریشه های فراکتالیته در رشد شبکه های پیچیده. نات. فیزیک 2006 ، 2 ، 275-281. [ Google Scholar ] [ CrossRef ]
شکل 1. نمونه ای از ساختار محلی شبکه.
شکل 2τمقادیر حاصل از مقایسه فهرست رتبه‌بندی تولید شده توسط شش معیار و فهرست رتبه‌بندی تولید شده توسط مدل SIR در هشت شبکه. فلش ها آستانه اپیدمی را نشان می دهد، βتی ساعت.��ℎ.الف ) ایمیل؛ ( ب ) توییتر؛ ( ج ) فیس بوک؛ ( د ) Epinions; ( ه ) وبلاگ؛ ( f ) ER; ( g ) WS; ( ح ) BA.
شکل 3τL��مقادیر شش اندازه گیری در پنج شبکه واقعی به عنوان L از 20 تا 500 متغیر است. ( الف ) ایمیل. ( ب ) توییتر؛ ( ج ) فیس بوک؛ ( د ) Epinions; ( ه ) وبلاگ.
جدول 1. زمان CPU (بر حسب ثانیه) شش اندازه گیری در پنج شبکه واقعی. 1
جدول 2. ویژگی های توپولوژیکی پایه هشت شبکه آزمایش شده.
جدول 3. مقادیر احتمال انتشار هشت شبکه.
جدول 4⟨ τ〈�〉ارزش ها و رتبه های شش معیار در هشت شبکه.
جدول 5⟨ τLبرای شش معیار در پنج شبکه واقعی ارزش و رتبه بندی می کند.
جدول 6. مقادیر D برای شش اندازه گیری در پنج شبکه واقعی.

بدون نظر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *