شناسایی کانال های ارتباطی موثر در شبکه های اجتماعی مبتنی بر انتشار پیام

مجله فناوری اطلاعات در طراحی مهندسی

مقاله 8، دوره 8، پائیز و زمستان 1394، اسفند 1394، صفحه 11-22

نوع مقاله: مقاله پژوهشی

نویسندگان

مهرداد جلالی¹؛ ریحانه ریگی^{* 2}؛ محمد حسین معطر²

¹دانشگاه آزاد اسلامی، مشهد

²گروه کامپیوتر

چکیده

شبکه اجتماعی یک ساختار اجتماعی از افراد و روابط بین آنهاست که در دنیای امروز نقش اساسی در گسترش اطلاعات ایفا می کنند. یک راه حل اساسی برای مطلع شدن از روند انتشار اطلاعات و اخبار در این شبکه ها، شناسایی یال های مهم و کلیدی بین اعضای جامعه است. در بسیاری از مقالات شناسایی یال ها به صورت ایستا صورت می گیرد که از جمله چالش ها مهم در این زمینه است و همچنین تعاملات بین کاربران در نظر گرفته نمی شود.
در این مقاله یک روش جدید برای شناسایی کانال های ارتباطی موثر معرفی می شود که قابلیت تطابق با شبکه های اجتماعی مختلف را دارد و با ساختار­های دنیای واقعی هماهنگ شده است. این روش بر اساس حجم اطلاعات منتقل شده بین اعضای جامعه به صورت پویا، مرکزیت بینابینی یال های ارتباطی و ویژگی های هر دو گره، کانال های ارتباطی موثر را شناسایی می کند. همچنین مدل ارائه شده در این مقاله می تواند اختصاصی بودن داده ها را حفظ کند. نتایج حاصل از ارزیابی نشان می دهد که این روش  نسبت به روش های مشابه نتایج مطلوبی دارد.

کلیدواژه‌ها

: آنالیز شبکه های اجتماعی؛ شناسایی کانل های ارتباطی موثر؛ شبکه اجتماعی

اصل مقاله

مقدمه

شبکه­های اجتماعی[1]بابهره ­گیری از جدیدترین تکنولوژی ‌ها و فناوری­ های جدید وب، راه ­حلی نوین جهت نمایش ارتباطات و تعاملات میان افراد می ­باشند. در دنیای ارتباطات‌، شبکه‌های اجتماعی را می‌توان بستری مفید در تولید و به اشتراک گذاری عقاید و عامل مهمی در رشد فردی و اجتماعی دانست. یک شبکه اجتماعی یک ساختار اجتماعی است که از گروه‌های مختلف فردی یا سازمانی تشکیل شده است این شبکه‌های فرامرزی امروزه به شدت مورد توجه کاربران قرارگرفته اند و هرروز بر میزان کارایی آنها و همینطور علاقمندی هوادارانشان افزوده می‌شود[1].

در دنیای امروز شبکه های اجتماعی نقش مهمی در تبادل اطلاعات بین افراد در یک جامعه بازی می کنند. شبکه های اجتماعی گونه ای از رسانه اجتماعی هستند که اخبار و اطلاعات به سرعت در آنها منتشر می شود. برای اطلاع از مسیر انتشار داده می توان یال های ارتباطی موثر را در شبکه یافت. شناسایی این یال ها مسئله مورد مطالعه در این مقاله است. در بسیاری از مقالات شناسایی یال ها به صورت ایستا صورت می گیرد که از جمله چالش ها مهم در این زمینه است و همچنین تعاملات بین کاربران در نظر گرفته نمی شود.

در مقالات  [2] و [3] برخی از روش های برای شناسایی کاربران با نفوذ، به عنوان مثال کاربرانی که قادر به تحریک دیگران هستند تا در فعالیت های شبکه های اجتماعی شرکت کنند و به طور فعال آنها را به کار گیرند، معرفی شده است. نویسندگان در[4] خواص اصلی گره هایی که در یک شبکه اجتماعی برخط واحد، گره های محیطی و گروه های محیطی را به بقیه شبکه متصل می کند، تجزیه و تحلیل کردند.

در سال های اخیر مطالعات زیادی پیرامون آنالیز شبکه های اجتماعی و معیارهای مرکزیت انجام شده است. مرکزیت بینابینی[2] یکی از محبوب ترین معیارها است و محاسبه آن جزء اصلی از طیف وسیعی از الگوریتم و برنامه های کاربردی است. برخی از نویسندگان مشکل محاسبه دقیق مقدار مرکزیت بینابینی برای هر یک از گره ها یا یال ها برای یک گراف بزرگ داده شده در حال رشد، را مطرح کردند. در مقاله [5] پیشنهاد انجام پیاده روی تصادفی[3] بر روی شبکه های اجتماعی برای محاسبه مقدار مرکزیت داده شد. در مقاله [6] یک  معیار مرکزیت یال جدید به نام k-path را معرفی می شود که این روش در مقاله [7] گسترش می یابد. در زمینه وب معنایی، مرکزیت یال برای کمیت قدرت روابط ارتباطی دو شی مفید است و در نتیجه می تواند برای کشف دانش های جدید مفید باشد[8].

در زمینه شبکه های اجتماعی، مرکزیت یال به مدل شدت رابطه اجتماعی میان دو نفرکمک می کند. در چنین مواردی، می توان از الگوهای تعاملات میان کاربران، جوامع مجازی استخراج را کنیم و با تجزیه و تحلیل آنها درک کنیم که چگونه یک کاربر قادر به نفوذ در دیگری است [6]. در سیستم های مبتنی بر دانش که داده ها را می توان به راحتی از طریق نمودار ها مدیریت کرد، روش وزن دهی به یال ها نقش کلیدی در شناسایی جوامع دارد، به عنوان مثال، گروه ای از گره های متراکم  که به یکدیگر متصل و با گره ساکن در خارج از جامعه خود همراهی ضعیفی دارند، جوامع را تشکیل می دهند [7].

بخشی از الگوریتم های تشخیص جامعه[4] مبتنی بر حذف یال هستند. به این ترتیب که با حذف یال های پر ترافیک جوامع در گراف اصلی شکل می گیرند. گریون [5]و نیومن[6] در [9] و [10] مرکزیت بینابینی راس را به منظور کشف ساختارهای جامعه، به یال تعمیم  دادند. این الگوریتم یکی از شناخته شده ترین الگوریتم ها برای پیدا کردن ساختار جامعه است که مبتنی بر حذف یال پر ترافیک است. سپس نیومن در [11] با بهره گیری از بردارهای ماتریس ویژه ساختار جامعه را در شبکه پیدا کرد. الگوریتم کنگا[7] در مقاله [12] برای کشف جوامع متداخل در شبکه، توسط گسترش الگوریتم گریون و ارائه شده است. این الگوریتم نیز، مانند الگوریتم اصلی خوشه بندی سلسله مراتبی انجام می دهد، اما اجازه می دهد تا جوامع با هم همپوشانی داشته باشند.

در مقاله [13] یک مشکل جدید به نام نفوذ تجمعی حداکثری کشف شده است که یک گام موثر برای نزدیک تر شدن به دنیای واقعی برنامه های بازاریابی ویروسی است. هدف این مقاله پیدا کردن مجموعه ای از کاربران اولیه است که از طریق نفوذ تجمعی حداکثری می توانند در یک دوره زمانی خاص تحریک شوند. در مقاله  [14] برای حل مشکل نفوذ حداکثری، یک قالب حداکثر محدویت نفوذ  ارائه شده است.

در ادامه در بخش 2 روش پیشنهادی مورد بررسی قرار می گیرد. نتایج به دست آمده در بخش 3 نشان داده شده و در بخش 4 نیز نتیجه گیری و کارهای آینده ارائه شده است.

2-روش پیشنهادی

شناسایی کانال های ارتباطی موثر برای اطلاع از مسیر انتشار اطلاعات بسیار مناسب است. این یال ها می توانند به عنوان گلوگاه های ارتباطی بین جوامع در شبکه های اجتماعی مطرح شوند. در این شبکه ها جوامع را می توان به عنوان گروه هایی از کاربران  که اغلب در تعامل با یکدیگراند شناخت. در این شبکه ها انتظار داریم که حجم اطلاعات منتقل شده در میان اعضای جامعه به طور قابل توجهی بالاتر از حجم اطلاعات منتقل شده بین اعضای جامعه و مردم خارج از جامعه باشد. توپولوژی شبکه به تنهایی می گوید که آیا دو کاربران  به هم متصل شده اند یا نه و در نتیجه دو کاربر می توانند به طور مستقیم  تبادل پیام داشته باشند یا نه. در واقع هیچ نشانه ای که آیا دو کاربر ارتباط برقرارکرده اند و بیشتر را فراهم نمی کند. به طور کلی، ما را در مورد وجود مسیر ترجیحی که در طول آن اطلاعات جریان  دارد، آگاه نیستیم[15]. بنابراین برای اطلاع از مسیر انتشار اطلاعات تعاملات برخط کاربران مورد بررسی قرار می گیرد. اگر بین دو گره پیامی منتقل شود، یک یال بین آنها شکل می گیرد و با افزایش تعداد پیام ها رابطه بین آنها تقویت می شود. اگر نرخ پیام های رد و بدل شده افزایش یابد، رابطه بین آنها تقویت شده و اگر نرخ پیام های منتقل شده کاهش یابد، رابطه بین آنها تضعیف می شود. در الگوریتم پیشنهادی برای شناسایی کانال های ارتباطی موثر از 3 پارامتر مرکزیت بینابینی یال، نرخ پیام های ارسال شده و شباهت بین دو گره استفاده می شود.

در محدوده نظریه گراف و تجزیه و تحلیل شبکه، انواع مختلفی از معیارهای مرکزیت راس در یک گراف وجود دارد، که اهمیت نسبی یک رأس در گراف را تعیین می کند. مهمترین معیار های مرکزیت، درجه، نزدیکی و بینابینی گره است که می توان آنها را برای یال نیز تعمیم داد [16]. مرکزیت بینابینی، تعداد بارهایی یک گره به عنوان یک پل در طول کوتاه ترین مسیر بین دو گره دیگر عمل می کند، تعریف می شود و به عنوان یک معیار برای تعیین کمیت کنترل یک انسان در ارتباط بین انسان های دیگر در یک شبکه اجتماعی توسط لینتون فریمن[8] در [17] معرفی شده است. رئوسی که به احتمال زیاد در کوتاهترین مسیری که به طور تصادفی بین دو راس که به طور تصادفی انتخاب شده، رخ می دهد، بینابینی بالایی دارد. به صورت فشرده تر بینابینی راس  را می تواند به صورت  معادله 1 نشان داد[18]:

     (1)        

 تعدادی کوتاهترین مسیرهای اتصال ازs به t و  تعداد کوتاهترین مسیرهای اتصال از s به t از طریق عبور از یالv است. اگر هیچ راه پیوستن از s و به t وجود نداشته باشد  است.

در سال 2002، گریون و نیومن تعریفی از مرکزیت بینابینیی یال در [9] ارائه کردند و همچنین حاشیه های مختلفی، از مرکزیت بینابینی، توسط  براندز پیشنهاد شده است[19]. با توجه به معادله معرفی شده در بالا، مرکزیت بینابینی یالe ϵ E  به این صورت تعریف می شود:

  (2)     

 تعدادی کوتاهترین مسیرهای اتصال ازs به t و  تعداد کوتاهترین مسیرهای اتصال از s به t از طریق عبور از یالe است. اگر هیچ راه پیوستن از S وبه t وجود نداشته باشد  است.

در این الگوریتم پیام های منتقل شده بین گره های شبکه

 مورد بررسی قرار می گیرد. اگر بین دو گره پیامی منتقل شود، یک یال بین آنها شکل می گیرد و با افزایش تعداد پیام ها رابطه بین آنها تقویت می شود. در بازه های زمانی مشخص شبکه بازنگری می شود اگر در این بازه زمانی پیامی منتقل شده باشد یال ارتباطی آنها تقویت می شود و اگر در این بازه زمانی هیج پیامی منتقل نشده باشد، رابطه بین آنها تضعیف می شود. بنابراین تعاملات بین کاربران به صورت پویا بررسی می شود و توپولوژی شبکه متناسب با رفتار کاربران مرتبا در حال تغییر است.

 

با مقایسه اطلاعات پروفایل کاربران در شبکه های اجتماعی می توان شباهت دو گره را محاسبه نمود. پروفایل کاربران می تواند شامل اطلاعاتی مانند سن، محل زندگی، میزان تحصیلات، شغل و... باشد.

با توجه به پارامترهای معرفی شده یک شاخص cut تعریف می کنیم که به این صورت بیان می شود:

      (3)

 مرکزیت بینابینی یال بین گره های  sو t است،  نرخ پیام های ارسال شده بین این دو گره است و  میزان شباهت بین آنهاست.

در الگوریتم پیشنهادی شاخص cut را برای هر یال محاسبه می کنیم سپس یک رتبه بندی بر اساس این شاخص انجام می دهیم. هر چه شاخص cut برای یک یال بیشتر باشد، به عنوان کانالی با کارایی بالاتر شناخته می شود. در واقع یال هایی با مقدار cut بالاتر به عنوان یال های بین خوشه ای مطرح می شوند و نقش مهمی در انتقال اطلاعات در شبکه اجتماعی بازی می کنند. شکل 1 نمایشی از الگوریتم پیشهادی می باشد که برای شناسایی کانال های ارتباطی موثر در شبکه های اجتماعی بکار می رود.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

شکل 1: نمایشی از روند الگوریتم پیشنهادی

الگوریتم پیشنهادی در زیر عنوان شده است.

الگوریتم پیشنهادی

در هر بازه زمانی T:

1- برای هر گره i و j :

    1-1- نرخ پیام های ارسالی در بازه زمانی T بین i و j محاسبه شود.

   1-2- اگر بین i و j در بازه زمانی T پیامی منتقل شده باشد، رابطه متناسب با تعداد پیام  ها تقویت می شود.

   1-3-اگر بین i و j در بازه زمانی T پیامی منتقل نشده باشد، رابطه متناسب با تعداد پیام ها تضعیف می شود و در نهایت یال ارتباطی آنها قطع می شود.

2- محاسبه شباهت بین هر دو گره i و j

3-محاسبه مرکزیت بینابینی یال بین هر دو گره i و j

4- محاسبه cut برای هر یال

5-رتبه بندی بر اساس شاخص cut

6- شناسایی یال های موثر در شبکه های اجتماعی

الگوریتم 1: الگوریتم پیشنهادی

بازه زمانی T باید متنایب تا ترافیک شبکه انتخاب شود. در اینجا بازه زمانی T، 6 ساعت در نظر گرفته شده است.

 

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

در این بخش ما آزمایشاتی که برای ارزیابی عملکرد الگوریتم پیشنهادی انجام شده را توصیف می کنیم. برای انجام آزمایشات، از 3 مجموعه داده که ویژگی های آنها در جدول1 گزارش شده است، استفاده کرده ایم.

 

3-1-معیار ازریابی پیمانه

در استراتژی های مبتنی بر پیمانه شبکه، یک معیار برای ارزیابی کیفیت پارتیشن بندی یک گراف G استفاده شده و هدف آن پیدا کردن پارتیشنی درG  است که حداکثر مقدار پیمانه یا Q را داشته باشد. عملکرد پیمانه شبکه به صورت زیر تعریف می شود:

 

      (4)

در اینجا m  تعداد کل یال ها درG و  ماتریس مجاورت G  است،  و  به ترتیب درجه رئوس i و j است و  نماد کرونکر است. در واقع، اگر i و j متعلق به جوامع مختلف باشند و باشد، طبق تعریف   می شود.  یک عدد حقیقی در فاصله [0,1]  است. به عنوان یک نتیجه، ما می توانیم تابع پیمانه Q به شرح زیر بازنویسی کنیم:

     (5)

که در آن   تعداد جوامع،  تعداد کل یال هایی که به رئوس داخل جامعه c پیوستن و  مجموع درجات رئوس تشکیل دهنده c است [7].

 

 

جدول 1: مجموعه داده های مورد استفاده

 

شماره	مجموعه داده	تعداد گره ها	تعداد پیام ها	وزن دهی بر اساس	جهت دار	نوع مجموعه داده	مرجع
1	Facebook-like Social Network	1899	59835	تعداد پیام ها	بله	شبکه اجتماعی آنلاین	[20]
2	Facebook-like Forum Network	899	33720	تعداد پیام ها	بله	شبکه اجتماعی آنلاین	[21]
2	Freeman’s EIES dataset	32	460	تعداد پیام ها	بله	شبکه اجتماعی آنلاین	[22]

 

 

در این بخش ما پیمانه به دست آمده توسط هر الگوریتم برای هر یک از این مجموعه داده ها را محاسبه کردیم. نتایج مربوطه در جدول 2 و شکل 2 گزارش شده است. از تجزیه و تحلیل این جدول نتیجه می گیریم که استفاده از الگوریتم پیشنهادی، منجر به نتایج بهتری شده است. عملکرد این روش بر روی مجموعه داده های بزرگ که برای آن بهینه سازی پیمانه ای به طور فزاینده ای سخت است، آزمایش شده و بهبود مطلوبی داشته است.

از تجزیه و تحلیل این جدول نتیجه می گیریم که استفاده از الگوریتم پیشنهادی، منجر به نتایج بهتری شده است. که می توان نتیجه گرفت بررسی پویای تعاملات می تواند تاثیر بسزایی در شناسایی کانال های موثر داشته باشد. عملکرد الگوریتم بر روی مجموعه داده های بزرگ که برای آن بهینه سازی پیمانه ای به طور فزاینده ای سخت است، آزمایش شده و بهبود مطلوبی داشته است. روش پیشنهادی به طور میانگین نسبت به الگوریتم لاوان 13.31%بهبود، نسبت به الگوریتم کپرا 16.92%، نسبت به الگوریتم اسلوم 18.8% بهبود و نسبت به الگوریتم گریون و نیومن 20.79% بهبود داشته است.

 

 

جدول2: پیمانه به دست آمده توسط هر الگوریتم برای هر یک از این مجموعه داده ها

Modularity	proposed algorithm	LM W [34]	CP W [34]	OS W [34]	GN [13]
Facebook-like Social Network (messages)	0.7364472	0.7194618	0.688295	0.6272956	0.543499
Facebook-like Forum Network (messages)	0.7642003	0.5776298	0.613864	0.6132854	0.714629
Freeman’s EIES dataset	0.8925422	0.6848853	0.539764	0.6367478	0.569106

 

 

 

شکل 2: نتایج پیمانه بدست آمده از روش های مختلف

 

 

 

3-2-معیار ارزیابیNMI

برای ارزیابی کیفیت نتایج از معیاری به نام اطلاعات متقابل نرمال شده یا NMI که توسط دانون[9] و همکاران در[23] معرفی شده است که ریشه در نظریه اطلاعات دارد، استفاده می شود.

در این معیار فرض بر این است که، با توجه به گراف G، یک حقیقت ضمنی به منظور بررسی جوامع در دسترس است. اجازه دهید A به عنوان یک ساختار جامعه درست در G  باشد و فرض کنید که G از  جامعه تشکیل شده است. یک الگوریتم تشخیص جامعه α را در نظر بگیریم. اجازه دهید که α را در G اجرا کرده و فرض کنیم که ساختار جامعه B متشکل از جامعه را شناسایی کنیم. ما یک  ماتریس CM  با ابعاد  تعریف می کنیم (که ماتریس سردرگمی[10] نامیده می شود) به طوری که در هر سطر از CM متناظر با یک جامعه در α و هر ستون CM مربوط به یک جامعه، در B است. عنصر عمومی برابر است با تعداد عناصر جامعه واقعی i ام  که همچنین در حال حاضر در جامعه j ام توسط الگوریتم قرار گرفته است. مجموع عناصر سطر i ام در ماتریس سردگمی است.اطلاعات متقابل نرمال شده توسط این تعریف شروع شده و به این صورت بیان می شود[15]:

  (6)   

نتایج حاصل از معیار ارزیابی NMI بر روی مجموعه داده Freeman’s EIES در جدول 3 و شکل 3 نشان داده شده است.

جدول 3: نتایج حاصل از معیار ارزیابی NMI

proposed algorithm	0.7820232
LM W [34]	0.6807359
CP W [34]	0.5849302
OS W [34]	0.6396628
GN [13]	0.5355508

 

 

شکل 3: نتایج حاصل از معیار ارزیابی NMI

از تجزیه و تحلیل این جدول نتیجه می گیریم که استفاده از الگوریتم پیشنهادی، منجر به نتایج بهتری شده است. که می توان نتیجه گرفت بررسی پویای تعاملات می تواند تاثیر بسزایی در شناسایی کانال های موثر داشته باشد. الگوریتم پیشنهادی نسبت به الگوریتم لاوان 10.12% بهبود، نسبت به الگوریتم کپرا 19.7%، نسبت به الگوریتم اسلوم 14.23% بهبود و نسبت به الگوریتم گریون و نیومن 24.64% بهبود داشته است.

4-نتیجه گیری و کارهای آینده

در این مقاله، روشی جهت شناسایی کانال هال ارتباطی موثر در شبکه های اجتماعی معرفی کرده ایم به طوری که قابلیت هماهنگی با پیچیدگی های دنیای واقعی را داشته باشد. یکی از مهمترین پارامترهای تعریف شده در این مقاله نرخ اطلاعات منتقل شده بین اعضای شبکه است. در این استراتژی، با توجه به تعداد پیام های منتقل شده بین کاربران، روابط بین گره های شبکه تقویت و یا تضعیف می شود. روش ارائه شده با کمترین اطلاعات ممکن از داده ها، کانال ها را شناسایی کند.

بسیاری از الگوریتم های موجود برای آنالیز شبکه های اجتماعی، ویژگی های توپولوژیکی شبکه را محاسبه می کنند که مطمئنا با زندگی واقعی قابل قیاس نیست. برای بهبود کیفیت شناسایی کانال هال ارتباطی موثر می توان به کشف ارتباط معنایی میان کاربران پراخت و محتوای پیام های ارسالی را نیز در نظر گرفت.

---

[1] Social networks

[2] Betweenness centrality

[3] Random walk

[4] Community Detection

[5] Girvan

[6] Newman

[7] CONGA

[8] Linton Freeman

[9] Danon

[10] Confusion Matrix

مراجع