تجزیه و تحلیل شبکه های اجتماعی - آکادمی علم داده نویان

تجزیه و تحلیل شبکه های اجتماعی: از نظریه گراف تا برنامه های کاربردی با پایتون

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

تئوری شبکه

ما با یک مقدمه کوتاه در مورد اجزای اصلی شبکه شروع می کنیم: گره ها(nodes) و لبه ها(edges) .

گره ‌ها (در مثال A، B، C، D، E) معمولا موجودیت ‌هایی را در شبکه نشان می ‌دهند و می ‌توانند ویژگی ‌های خود (مانند وزن، اندازه، موقعیت و هر ویژگی دیگر) و همچنین ویژگی‌ های مبتنی بر شبکه (مانند درجه- شماره همسایگان یا خوشه (cluster)- یک جزء متصل که گره به آن تعلق دارد و غیره) را داشته باشند.

لبه‌ ها نشان ‌دهنده اتصالات بین گره‌ ها هستند و ممکن است ویژگی ‌هایی را نیز داشته باشند (مانند وزن نشان دهنده قدرت اتصال، جهت در صورت وجود رابطه نا متقارن یا زمان در صورت وجود).

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

شبکه های دنیای واقعی

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

پدیده جهان کوچک ادعا می کند که شبکه های واقعی اغلب مسیر های بسیار کوتاهی (از نظر تعداد پرش) بین اعضای شبکه متصل دارند. این امر برای شبکه های اجتماعی واقعی و مجازی (تئوری شش درجه جدایی یا the six handshakes) و برای شبکه های فیزیکی مانند فرودگاه ها یا برق مسیریابی ترافیک وب صدق می کند.
شبکه ‌های بدون مقیاس یا Networks Scale Free با توزیع درجه قانون قدرت، جمعیتی منحرف با چند گره بسیار متصل (مانند تأثیرات اجتماعی) و تعداد زیادی گره‌ های به هم پیوسته دارند.
هموفیلی یا Homophily تمایل افراد به معاشرت و پیوند با دیگران مشابه خود است که منجر به خواص مشابه در بین همسایگان می شود.

اقدامات مرکزیت

گره های بسیار مرکزی نقش کلیدی یک شبکه را ایفا می کنند و به عنوان هاب برای پویایی های مختلف شبکه عمل می کنند. با این حال، تعریف و اهمیت مرکزیت ممکن است از موردی به مورد دیگر متفاوت باشد و ممکن است به معیار های مرکزی متفاوت اشاره داشته باشد:

درجه یا Degree – مقدار همسایگان گره
EigenVector / PageRank – دایره های تکراری همسایگان
نزدیکی یا Closeness – سطح نزدیکی به همه گره ها
بین یا Betweenness – مقدار مسیر کوتاهی که از گره می گذرد

تصویری از اقدامات مختلف مرکزیت.

معیار های مختلف می تواند در سناریو های مختلف مانند رتبه بندی وب (رتبه صفحه)، تشخیص نقاط بحرانی (بین)، هاب های حمل و نقل (نزدیک بودن) و سایر برنامه ها مفید باشد.

ساخت یک شبکه

شبکه ‌ها را می‌ توان از مجموعه داده‌ های مختلف ساخت، تا زمانی که بتوانیم روابط بین گره‌ ها را توصیف کنیم. در مثال زیر شبکه رأی ‌های یوروویژن 2018 (بر اساس داده ‌های رسمی) را با بسته Python networkx می ‌سازیم و تجسم می ‌کنیم.

ما داده ‌ها را از فایل اکسل به یک دیتافریم پاندا می ‌خوانیم تا نمایشی جدولی از آرا به دست آوریم. از آنجایی که هر ردیف نشان دهنده تمام آرای هر کشور است، مجموعه داده را ذوب melt می کنیم تا مطمئن شویم که هر ردیف نشان دهنده یک رای (لبه) بین دو کشور (گره) است.

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

1 votes_data = pd.read_excel(‘ESC2018_GF.xlsx’,sheetname=’Combined result’)

3 votes_melted = votes_data.melt(

4 [‘Rank’,’Running order’,’Country’,’Total’],

5 var_name = ‘Source Country’,value_name=’points’)

7 G = nx.from_pandas_edgelist(votes_melted,

8 source=’Source Country’,

9 target=’Country’,

10 edge_attr=’points’,

11 create_using=nx.DiGraph())

13 nx.draw_networkx(G)

بارگیری شبکه یوروویژن از فایل اکسل

nx.draw_networkx(G) نتیجه در شبکه رأی گیری یوروویژن 2018

تجسم

متأسفانه روش ترسیم داخلی به شکل نتیجه ای بسیار نا مفهومی منجر می شود. این روش سعی می ‌کند یک نمودار بسیار مرتبط ترسیم کند، اما بدون هیچ «اشاره ‌های hints» مفیدی نمی ‌تواند از داده‌ ها معنای زیادی پیدا کند. ما با تقسیم و غلبه بر جنبه های بصری مختلف طرح با دانش قبلی که در مورد موجودیت ها داریم، شکل را بهبود خواهیم بخشید:

موقعیت – هر کشور بر اساس موقعیت جغرافیایی آن تعیین می شود
سبک – هر کشور با رنگ پرچم و پرچم خود شناخته می شود
اندازه – اندازه گره ها و لبه ها نشان دهنده تعداد نقاط است

در نهایت، اجزای شبکه را در بخش ‌هایی ترسیم می ‌کنیم:

countries = pd.read_csv(‘countries.csv’,index_col=’Country’)

3 pos_geo = { node:

4 ( max(-10,min(countries.loc[node][‘longitude’],55)), # fixing scale

5 max(countries.loc[node][‘latitude’],25)) #fixing scale

6 for node in G.nodes() }

7 pos_geo = {}

9 for node in G.nodes():

10 pos_geo[node] = (

11 max(-10,min(countries.loc[node][‘longitude’],55)), # fixing scale

12 max(countries.loc[node][‘latitude’],25) #fixing scale )

14 flags = {}

15 flag_color = {}

16 for node in tqdm.tqdm_notebook(G.nodes()):

17 flags[node] = ‘flags/’+(countries.loc[node][‘cc3’]).lower().replace(‘ ‘,”)+’.png’

18 flag_color[node] = ColorThief(flags[node]).get_color(quality=1)

20 def RGB(red,green,blue):

21 return ‘#%02x%02x%02x’ % (red,green,blue)

23 ax=plt.gca()

24 fig=plt.gcf()

25 plt.axis(‘off’)

26 plt.title(‘Eurovision 2018 Final Votes’,fontsize = 24)

28 trans = ax.transData.transform

29 trans2 = fig.transFigure.inverted().transform

31 tick_params = {‘top’:’off’, ‘bottom’:’off’, ‘left’:’off’, ‘right’:’off’,

32 ‘labelleft’:’off’, ‘labelbottom’:’off’} #flag grid params

34 styles = [‘dotted’,’dashdot’,’dashed’,’solid’] # line styles

36 pos = pos_geo

38 # draw edges

39 for e in G.edges(data=True):

40 width = e[2][‘points’]/24 #normalize by max points

41 style=styles[int(width*3)]

42 if width>0.3: #filter small votes

43 nx.draw_networkx_edges(G,pos,edgelist=[e],width=width, style=style, edge_color = RGB(*flag_color[e[0]]) )

44 # in networkx versions >2.1 arrowheads can be adjusted

46 #draw nodes

47 for node in G.nodes():

48 imsize = max((0.3*G.in_degree(node,weight=’points’)

49 /max(dict(G.in_degree(weight=’points’)).values()))**2,0.03)

51 # size is proportional to the votes

52 flag = mpl.image.imread(flags[node])

54 (x,y) = pos[node]

55 xx,yy = trans((x,y)) # figure coordinates

56 xa,ya = trans2((xx,yy)) # axes coordinates

58 country = plt.axes([xa-imsize/2.0,ya-imsize/2.0, imsize, imsize ])

59 country.imshow(flag)

60 country.set_aspect(‘equal’)

61 country.tick_params(**tick_params)

63 fig.savefig(‘images/eurovision2018_map.png’)

رقم جدید کمی خواناتر است و مروری کوتاه بر آرا را به ما می دهد. به عنوان یک یادداشت جانبی کلی، ترسیم شبکه ها اغلب سخت است و نیاز به انجام مبادلات متفکرانه بین مقدار داده ارائه شده و پیام ارسال شده دارد. (می توانید سایر ابزار های تجسم شبکه مانند Gephi، Pyvis یا GraphChi را کاوش کنید).

جریان اطلاعات

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

آستانه خطی Linear Threshold یک رفتار مبتنی بر آستانه را تعریف می کند، جایی که تأثیر از چندین همسایه گره جمع می شود، که تنها در صورتی فعال می شود که تأثیر تجمعی از آستانه خاصی عبور کند. چنین رفتاری برای توصیه های فیلم معمول است، جایی که یک نکته از یکی از دوستان شما ممکن است در نهایت شما را متقاعد کند که یک فیلم را ببینید، پس از شنیدن تعریف های زیاد در مورد آن.

تابع فعال سازی آستانه خطی

در مدل آبشار مستقل (Independent Cascade model)، هر یک از همسایگان فعال گره شانس احتمالی و مستقلی برای فعال کردن گره دارند. این شبیه یک ویروس واگیر دار است، مانند کووید 19، که در آن هر یک از تعاملات اجتماعی ممکن است باعث عفونت شود.

مثال جریان اطلاعات

برای نشان دادن فرآیند انتشار اطلاعات، از شبکه Storm of Swords بر اساس شخصیت ‌های نمایش بازی تاج و تخت استفاده می‌ کنیم. این شبکه بر اساس حضور مشترک در کتاب های «آواز یخ و آتش» ساخته شد.

روند شماتیک ایجاد شبکه Game of Thrones

با تکیه بر مدل آبشار مستقل، سعی خواهیم کرد پویایی شایعات را که در این نمایش بسیار رایج است، ردیابی کنیم.

هشدار اسپویل! فرض کنید جان اسنو در ابتدای کار چیزی نمی داند، در حالی که دو دوست وفادارش، برن استارک و سامول تارلی، راز بسیار مهمی را در مورد زندگی او می دانند. بیایید تماشا کنیم که چگونه این شایعه تحت مدل آبشار مستقل پخش می شود:

1 def independent_cascade(G,t,infection_times):

2 #doing a t->t+1 step of independent_cascade simulation

3 #each infectious node infects neigbors with probabilty proportional to the weight

4 max_weight = max([e[2][‘weight’] for e in G.edges(data=True)])

5 current_infectious = [n for n in infection_times if infection_times[n]==t]

6 for n in current_infectious:

7 for v in G.neighbors(n):

8 if v not in infection_times:

9 if G.get_edge_data(n,v)[‘weight’] >= np.random.random()*max_weight:

10 infection_times[v] = t+1

11 return infection_times

14 infection_times = {‘Bran-Stark’:-1,’Samwell-Tarly’:-1,’Jon-Snow’:0}

16 for t in range(10):

17 plot_G(subG,pos,infection_times,t)

18 infection_times = independent_cascade(subG,t,infection_times)

کد شبیه سازی فرآیند آبشار مستقل

این شایعه در t=1 به Jon می رسد، در مراحل زمانی زیر به همسایگانش سرایت می کند و به سرعت در سراسر شبکه پخش می شود و در نتیجه به یک دانش عمومی تبدیل می شود:

انتشار مستقل آبشار در شبکه Game of Thrones

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

حداکثر سازی تأثیر

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

این تأثیر گذاران یا اینفلوئنسر ها را می ‌توان با تکنیک ‌های متعددی، مانند استفاده از معیار های مرکزیت که در بالا ذکر کردیم، شناسایی کرد. در اینجا مرکزی ترین گره ها در شبکه Game of Thrones با توجه به معیار های مختلف آورده شده است:.

معیار های مرکزیت در شبکه بازی تاج و تخت

همانطور که می بینیم، برخی از شخصیت ها در سطوح مختلف ظاهر می شوند و همچنین به دلیل تأثیر اجتماعی خود در نمایش شناخته شده هستند.

با شبیه ‌سازی انتخاب بیشتر گره ‌های مرکزی، مشاهده می ‌کنیم که انتخاب یک گره از شبکه می ‌تواند حدود ۵۰ درصد از پوشش شبکه را به دست آورد – این همان تأثیرگذاران اجتماعی مهم هستند.

پوشش نفوذ شبکه با روش ها و بودجه های مختلف

از سوی دیگر، حداکثر سازی نفوذ، سخت است. در واقع به عنوان یک مشکل NP-Hard در نظر گرفته می شود. بسیاری از اکتشافات برای یافتن بهترین مجموعه بذر در یک محاسبه کارآمد توسعه داده شدند. تلاش از روش brute-force برای یافتن بهترین زوج کاشت در شبکه ما منجر به صرف 41 دقیقه و دستیابی به 56٪ پوشش (با انتخاب Robert Baratheon و Khal Drogo) شد، نتیجه ای که دستیابی به آن با اکتشافی مرکزی دشوار است.

جمع بندی

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

منابع مفید

کد و داده ها:

مجموعه داده بازی تاج و تخت @jeffreylancaster
آموزش شبکه ها @MridulS
پرچم‌گذاری تصاویر @linssen
داده های یوروویژن

اوراق:

دیدگاهتان را بنویسید لغو پاسخ