بخشی از مقاله
خلاصه
امروزه به دلیل اهمیت انتشار اطلاعات، پیدا کردن گرههای تاثیرگذار در شبکههای اجتماعی که منجر به انتشار بیشتر اطلاعات در بین گرههای شبکه می شود از اهمیت بسزایی برخوردار است. در این زمینه روشهای مختلفی وجود دارد که می توان به درجه گره، مرکزیت میانی - betweenness centrality - و مرکزیت نزدیکی - closeness centrality - اشاره کرد.در این مقاله با استفاده از مدل انتشار اطلاعات آبشاری مستقل - - Independent Cascade Model و روشهای شناسایی اجتماعات مختلف، به ارائه روشی در شناسایی گرههای تاثیرگذار پرداختهایم. این روش به بررسی وضعیت موقعیت مکانی گره در شبکه میپردازد و بر این اساس گروهکهایی - - Cliques با بیشترین ارتباط را در اجتماعات شناسایی میکند. گرههایی که بیشترین گروهکها را باهم مرتبط میکنند، به عنوان گرههای آغازگر کننده شیوع انتخاب میشوند. دادههای مورد استفاده برای ارزیابی روشها، دادههای یک شبکه پستالکترونیکی دانشگاهی در اسپانیا بوده است. نتایج حاصل از پیادهسازیها افزایش میزان انتشار در این شبکه را نشان میدهند.
کلمات کلیدی: شبکه اجتماعی، انتشار اطلاعات، شناسایی اجتماعات، خوشهبندی، گره تاثیرگذار، مدلآبشاری مستقل
.1 مقدمه
درک ساختارشبکه و روابط بین آنها توجه بسیاری را اخیرا مورد توجه قرار داده است.[1]-[5] پیداکردن گرههای تاثیرگذار در مکانیسمهای مثل آبشاری و انتشار از اهمیت بالایی برخوردار است.[6]-[11] پیدا کردن گرههای تاثیرگذار علاوه بر اهمیت تئوری ارزش عملی نیز دارد: برای کنترل شایعات، کنترل انتشار بیماری ها و ایجاد ابزارهای مارکتینگ استفاده میشود. درجه گره یک روش ساده و کارا برای انتخاب گره تاثیرگذار است اما درجه گره خیلی روش مناسبی نیست چون ممکن است یک گره که همسایه های تاثیر گذار کمتری دارد تاثیر بیشتری از گرهی که همسایه های بیشتری دارد داشته باشد. .[12]اگرچه روش های دیگری مانند مرکزیت میانی و مرکزیت نزدیکی وجود دارند که روش های خوبی هستند اما چون پیچیدگی محاسباتی بالایی دارند برای شبکه های با مقیاس بالا مناسب نمی باشند.
در این زمینه, لو و همکاران [13] روشی بر مبنای گام تصادفی1 پیشنهاد دادهاند که leaderrank نام دارد که این روش مانند pagerank[14] برای شبکههای جهتدار جواب مناسبی میدهد اما برای شبکه های غیرجهت دار مناسب نیست. در این پژوهش از روشهای شناسایی اجتماعات : الگوریتم چندمرحلهای [15]، ، پخش برچسب[16] و الگوریتم مرکزیت میانی یال[17] برای انتخاب گره های تاثیرگذار در شبکه استفاده شده است. ساختار متراکم اجتماعات و ارتباطات بیشتر گرهها در آنها سبب می شود از پخش اطلاعات در بخش های مختلف شبکه اطمینان بیشتری حاصل گردد. همچنین الگوریتم گرههای مرزی مبتنی بر گروهک و بیشینه درجه همسایه گره، با هدف شناسایی گرههای تأثیرگذار در شبکهها بر اساس ساختار اجتماعات یک شبکه ارائه شدهاست. نتایج حاصل از این الگوریتمها با نتایج حاصل از الگوریتم مبتنی بر مرکزیت و الگوریتم روش تفکیک حول محور گره مرکزی2 مقایسه شدهاست. نتایج این مقاله انتشار اطلاعات بیشتری را نسبت به دیگر روشها نشان میدهد.
ایده اصلی این مقاله به صور زیر است:
1؛ ایده جدیدی ارائه شده است که بر مبنای گروهک3 است چون خاصیت گروهک آن است که گرهها ارتباطات بیشتری با هم دارند در نتیجه می تواند اطلاعات بیشتری را انتشار دهد.
2؛ روشهای شناسایی اجتماعات مختلف برای پیدا کردن نودهای اغازین تاثیرگذار و همچنین الگوریتمهای مبتنی بر مرکزیت و الگوریتم روش تفکیک حول محورگره مرکزی پیاده سازی شده است و با روش ارائه شده در این مقاله مقایسه شده است.
.2 کارهای انجام شده در زمینه انتشار اطلاعات
برای یافتن تأثیرگذارترین گرهها همچنین مدلی بر مبنای مدل آبشاری مستقل معرفی شد.[18] در این مدل با استفاده الگوریتم حریصانه با ساختار SR-community، ابتدا اجتماعات موجود در شبکه شناسایی میشوند. سپس با استفاده از الگوریتم حریصانه و اجتماعات یافت شده توسط SR-community مؤثرترین گرهها را در روند انتشار مییابد.-SR community دنبالهای از مجموعه گرههایی است که اتصال محکم و زیادی دارند. تانگ و همکاران[19] روی شبکههای متغیر تمرکز نمودند و متغیرهای نزدیکی موقتیو4 بینیّت موقتی5 را به عنوان معیار انتخاب گرهها تعریف کردند که برای یافتن گرههای تاثیرگذار، تعاملات پویا را در طول زمان در نظر میگیرد.
یونکی و کیم[20] ابتدا مشکل افزایش تأثیر انتشار را به عنوان مسئله انتخاب بهترین و تأثیرگذارترین گرههای اولیه معرفی میکنند و به انتخاب همسایههای تأثیرگذار6 به عنوان نوع دیگری از IM میپردازند، یعنی انتخاب مؤثرترین همسایههای گرههای شروعکننده انتشار. سپس به بررسی چهار استراتژی انتخاب تصادفی7، انتخاب درجه8، انتخاب ظرفیت9 و انتخاب ظرفیت وزندار10 برای انتخاب مؤثرترین همسایهها در شرایط و شبکههای مختلف میپردازند و نتایج حاصل را برای انتخاب بهترین استراتژی انتخاب همسایهها در شرایط مختلف مقایسه مینمایند.از جمله روشهای اکتشافی که در زمینه شناسایی گرههای تاثیرگذار با استفاده از شناسایی اجتماعات ارائه شدهاند میتوان به روش انتخاب گرهها بر اساس مرکزیت نزدیکی، تعداد یالهایشان به دیگر اجتماعات و درجه گره اشاره کرد.[21]
قانون 80/20 عنوان میکند که 80درصد یالها به 20درصد از گرهها تعلق دارد. بنابرین %20 از گرههای دارای بیشترین درجه انتخاب شده و اجتماعاتی که این گرهها به آنها تعلق دارند مشخص میشود. سپس اجتماعات بر اساس نسبت تعداد ارتباطات داخلی این گرهها به ارتباطات خارجی آنها مشخص میشود. سپس با استفاده از روشهای شناسایی اجتماعات اشاره شده، گرههای تاثیرگذار هر اجتماع مشخص میشوند. تعداد گرههای مورد نیاز به عنوان پارامتر ورودی مشخص میشود. نشان دادهشدهاست که این سه روش نسبت به روش حریصانه سرعت بیشتر و در عین حال نتیجهای تقریبا مشابه دارند.
در سال 2011 انجرانی و معینی[21] روشی بر مبنای شناسایی اجتماعات بر اساس نسبت تعداد ارتباطات داخلی این گرهها به ارتباطات خارجی آنها و انتخاب گرهها بر اساس مرکزیت نزدیکی، تعداد یالهایشان به دیگر اجتماعات و درجه گره ارائه دادند. برای انتخاب تاثیرگذارترین گرهها روشی[22] ارائه شد که در آن بین هر جفت گره، از احتمال انتقال اطلاعات و همینطور الگوریتم خوشه بندی K-Medoid استفاده میکند. در این روش نشان داده شده است که با استفاده از روش K-Medoid میتوان گرههای بیشتری از شبکه را نسبت به الگوریتم حریصانه تحت تاثیر قرار داد.
