گراف علم داده با پایتون/NetworkX

ما غرق داده ایم پایگاه‌های اطلاعاتی و صفحات گسترده در حال گسترش مملو از بینش‌های پنهان تجاری است. چگونه می‌توانیم داده‌ها را تجزیه و تحلیل کنیم و نتیجه‌گیری کنیم در حالی که تعداد زیادی از آن‌ها وجود دارد؟ نمودارها (شبکه ها، نه نمودارهای میله ای) رویکردی زیبا ارائه می دهند.

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

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

اعتبار تصویر سمت راست: ALBANESE, Federico, et al. “پیش بینی افراد در حال تغییر با استفاده از متن کاوی و یادگیری ماشین نمودار در توییتر.” (24 آگوست 2020): arXiv:2008.10749 [cs.SI]

پس چگونه توسعه دهندگان می توانند از علم داده های نموداری استفاده کنند؟ بیایید به پرکاربردترین زبان برنامه نویسی علم داده: پایتون

شروع کار با گراف‌های «تئوری گراف» در پایتون

توسعه دهندگان پایتون چندین کتابخانه داده گراف مانند NetworkX، igraph، SNAP و graph-tool در دسترس خود دارند. جدا از جوانب مثبت و منفی، آنها رابط های بسیار مشابهی برای مدیریت و پردازش ساختارهای داده گراف پایتون دارند.

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

ایجاد یک نمودار جدید با NetworkX ساده است:

import networkx as nx
G = nx.Graph()

ولی G هنوز گراف چندانی ندارد، زیرا فاقد گره و یال است.

نحوه اضافه کردن گره ها به یک نمودار

می‌توانیم با زنجیر کردن مقدار بازگشتی، یک گره به شبکه اضافه کنیم Graph() با .add_node() (یا .add_nodes_from() برای چندین گره در یک لیست). همچنین می‌توانیم با ارسال یک دیکشنری به عنوان پارامتر، ویژگی‌ها یا ویژگی‌های دلخواه را به گره‌ها اضافه کنیم، همانطور که با نشان می‌دهیم. node 4 و node 5:

G.add_node("node 1")
G.add_nodes_from(["node 2", "node 3"])
G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})])
print(G.nodes)
print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

این خروجی خواهد داشت:

['node 1', 'node 2', 'node 3', 'node 4', 'node 5']
123

اما بدون لبه‌های بین گره‌ها، آنها ایزوله هستند و مجموعه داده‌ها بهتر از یک جدول ساده نیست.

نحوه اضافه کردن لبه به نمودار

مشابه تکنیک گره ها، می توانیم از آن استفاده کنیم .add_edge() با نام دو گره به عنوان پارامتر (یا .add_edges_from() برای چندین یال در یک لیست)، و به صورت اختیاری یک فرهنگ لغت از ویژگی ها را شامل شود:

G.add_edge("node 1", "node 2")
G.add_edge("node 1", "node 6")
G.add_edges_from([("node 1", "node 3"), 
                  ("node 3", "node 4")])
G.add_edges_from([("node 1", "node 5", {"weight" : 3}), 
                  ("node 2", "node 4", {"weight" : 5})])

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

NetworkX تمام لبه ها را هنگام استفاده فهرست می کند G.edges، اما شامل صفات آنها نمی شود. اگر ویژگی های لبه را بخواهیم، ​​می توانیم استفاده کنیم G[node_name] برای دریافت هر چیزی که به یک گره یا G[node_name][connected_node_name] برای بدست آوردن ویژگی های یک یال خاص:

print(G.nodes)
print(G.edges)
print(G["node 1"])
print(G["node 1"]["node 5"])

این خروجی خواهد داشت:

['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6']
[('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')]
{'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}}
{'weight': 3}

اما خواندن اولین نمودار ما به این شکل غیر عملی است. خوشبختانه، بازنمایی بسیار بهتری وجود دارد.

نحوه تولید تصاویر از نمودارها (و نمودارهای وزنی)

تجسم گراف ضروری است: به ما امکان می دهد روابط بین گره ها و ساختار شبکه را سریع و واضح ببینیم.

یک تماس سریع به nx.draw(G) تمام چیزی که لازم است:

بیایید لبه‌های سنگین‌تر را به همان نسبت ضخیم‌تر کنیم nx.draw() زنگ زدن:

weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()]
nx.draw(G, width=weights)

همانطور که در نتیجه مشاهده می شود، یک ضخامت پیش فرض برای لبه های بدون وزن ارائه کردیم:

روش‌ها و الگوریتم‌های نمودار ما در شرف پیچیده‌تر شدن هستند، بنابراین گام بعدی استفاده از مجموعه داده‌های شناخته شده‌تر است.

نمودار علم داده با استفاده از داده های فیلم جنگ ستارگان: قسمت چهارم

برای آسان‌تر کردن تفسیر و درک نتایج، از آن استفاده می‌کنیم این مجموعه داده. گره ها شخصیت های مهم را نشان می دهند و لبه ها (که در اینجا وزن ندارند) نشان دهنده حضور مشترک در یک صحنه است.

توجه: مجموعه داده از Gabasova، E. (2016) است. جنگ ستارگان شبکه اجتماعی. DOI: https://doi.org/10.5281/zenodo.1411479.

ابتدا داده ها را با استفاده از آن تجسم می کنیم nx.draw(G_starWars, with_labels = True):

کاراکترهایی که معمولاً با هم ظاهر می شوند، مانند R2-D2 و C-3PO، به نظر می رسد که به طور نزدیک به هم متصل هستند. در مقابل، می‌توانیم ببینیم که دارث ویدر صحنه‌هایی را با اوون به اشتراک نمی‌گذارد.

طرح‌بندی تجسم شبکه ایکس پایتون

چرا هر گره در جایی که در نمودار قبلی است قرار دارد؟

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

NetworkX طرح‌بندی‌های دیگری دارد که از معیارهای مختلفی برای موقعیت‌یابی گره‌ها استفاده می‌کنند، مانند circular_layout:

pos = nx.circular_layout(G_starWars)
nx.draw(G_starWars, pos=pos, with_labels = True)

نتیجه:

این طرح به این معنا خنثی است که مکان یک گره به اهمیت آن بستگی ندارد – همه گره ها به طور مساوی نشان داده می شوند. (طرح دایره ای همچنین می تواند به تجسم مجزا کمک کند اجزای متصل– زیرگراف‌هایی که یک مسیر بین هر دو گره دارند – اما در اینجا، کل نمودار یک جزء بزرگ متصل است.)

هر دو طرح‌بندی که دیده‌ایم درجه‌ای از درهم‌ریختگی بصری دارند، زیرا لبه‌ها آزادانه از لبه‌های دیگر عبور می‌کنند. اما Kamada-Kawai، یکی دیگر از الگوریتم‌های هدایت‌شده نیرو مانند spring_layout، گره ها را طوری قرار می دهد که انرژی سیستم را به حداقل برساند.

این تلاقی لبه ها را کاهش می دهد اما قیمت دارد: کندتر از طرح بندی های دیگر است و بنابراین برای نمودارهایی با گره های زیاد توصیه نمی شود.

این یک تابع ترسیم تخصصی دارد:

nx.draw_kamada_kawai(G_starWars, with_labels = True)

که در عوض این شکل را ایجاد می کند:

بدون هیچ مداخله خاصی، الگوریتم شخصیت های اصلی (مانند لوک، لیا و C-3PO) را در مرکز قرار می دهد و شخصیت های کمتر برجسته (مانند Camie و ژنرال دودونا) را در کنار مرز قرار می دهد.

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

تجزیه و تحلیل گره: درجه و رتبه صفحه

اکنون که می توانیم شبکه خود را به وضوح تجسم کنیم، ممکن است برای ما جالب باشد که گره ها را مشخص کنیم. معیارهای متعددی وجود دارد که ویژگی‌های گره‌ها و در مثال ما، کاراکترها را توصیف می‌کنند.

یکی از معیارهای اساسی برای یک گره، آن است درجه: چند لبه دارد درجه a جنگ ستارگان گره کاراکتر اندازه گیری می کند که با چند شخصیت دیگر صحنه را به اشتراک گذاشته است.

را degree() تابع می تواند درجه یک کاراکتر یا کل شبکه را محاسبه کند:

print(G_starWars.degree["LUKE"])
print(G_starWars.degree)

خروجی هر دو دستور:

15
[('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

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

print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

خروجی:

[('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

از آنجایی که مدرک فقط یک کل است، جزئیات تک تک لبه ها را در نظر نمی گیرد. آیا یک لبه داده شده به یک گره جدا شده یا به گره ای که به کل شبکه متصل است متصل می شود؟ الگوریتم PageRank گوگل این اطلاعات را جمع آوری می کند تا میزان “مهم” بودن یک گره در شبکه را بسنجد.

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

چنین گره هایی رتبه صفحه بالاتری خواهند داشت که می توانیم آن را با کتابخانه NetworkX محاسبه کنیم:

pageranks = nx.pagerank(G_starWars) # A dictionary
print(pageranks["LUKE"])
print(sorted(pageranks, key=lambda x: x[1], reverse=True))

این رتبه لوک و شخصیت های ما را بر اساس رتبه مرتب می کند:

0.12100659993223405
['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

اوون شخصیتی است که بالاترین رتبه صفحه را دارد و از لوک که بالاترین درجه را داشت پیشی می گیرد. تحلیل: اگرچه اوون شخصیتی نیست که بیشترین صحنه ها را با شخصیت های دیگر به اشتراک بگذارد، اما او شخصیتی است که صحنه هایی را با بسیاری از شخصیت های مهم مانند خود لوک، R2-D2 و C-3PO به اشتراک می گذارد.

در تضاد بیشتر، C-3PO، کاراکتری با بالاترین درجه سوم، شخصیتی است که کمترین رتبه صفحه را دارد. علیرغم اینکه C-3PO ارتباطات زیادی دارد، بسیاری از آنها با شخصیت های بی اهمیت هستند.

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

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

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

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

برچسب ها در شبکه پخش می شوند تا زمانی که همه گره ها یک برچسب را با اکثر همسایگان خود به اشتراک بگذارند. گروه‌هایی از گره‌هایی که نزدیک به یکدیگر متصل هستند، در نهایت دارای یک برچسب هستند.

با کتابخانه NetworkX، اجرای این الگوریتم تنها به سه خط پایتون نیاز دارد:

from networkx.algorithms.community.label_propagation import label_propagation_communities

communities = label_propagation_communities(G_starWars)
print([community for community in communities])

خروجی:

[{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

در این لیست از مجموعه ها، هر مجموعه نشان دهنده یک جامعه است. خوانندگانی که با فیلم آشنا هستند متوجه خواهند شد که الگوریتم توانسته است «آدم‌های خوب» را از «بچه‌های بد» کاملاً جدا کند و شخصیت‌ها را به‌طور معنی‌داری بدون استفاده از برچسب یا ابرداده واقعی (جامعه) متمایز کند.

بینش هوشمند با استفاده از علم داده های نمودار در پایتون

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

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

مطالعه توصیه شده در علم داده های نمودار

الگوریتم های تشخیص جامعه
ژائو یانگ، رنه آلگشایمر ​​و کلودیو تسونه. “تحلیل مقایسه ای الگوریتم های تشخیص جامعه در شبکه های مصنوعی” گزارش های علمی، 6، شماره. 30750 (2016).

نمودار یادگیری عمیق
توماس کیپف. “نمودار شبکه های کانولوشنال” 30 سپتامبر 2016.

کاربردهای علم داده های نموداری
آلبانیز، فدریکو، لئاندرو لومباردی، استبان فوئرشتاین و پابلو بالنزوئلا. “پیش بینی افراد در حال تغییر با استفاده از متن کاوی و یادگیری ماشین نمودار در توییتر.” (24 اوت 2020): arXiv:2008.10749 [cs.SI].

کوهن، الیور. “PyData Tel Aviv Meetup: Node2vec.” یوتیوب. 22 نوامبر 2018. ویدئو, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.