Дослідження та аналіз мереж за допомогою Python
Автори: Джон Ледд, Джессіка Отіс, Крістофер Воррен і Скотт Вайнґарт Переклали на українську: Орися Віра та Гліб Солоджук Оригінал уроку: https://programminghistorian.org/en/lessons/exploring-and-analyzing-network-data-with-python
У цьому уроці представлено метрики мереж та їх аналіз для обробки даних у гуманітарних науках. Ви дізнаєтесь, як використовувати пакет NetworkX Python для створення та роботи з характеристиками мереж.
Вступ
Цілі уроку
У цьому уроці ви дізнаєтесь: Як використовувати пакет NetworkX для роботи з мережами в Python; Як аналізувати мережі на основі даних з гуманітарних наук, щоб знайти: - Структуру мережі та довжину шляху, - Важливі або центральні вершини, і - Спільноти та підгрупи.
Примітка: цей урок призначений для вивчення характеристик та метрик мережі. Тому ми зосередимося на способах аналізу мереж без візуалізації. Ймовірно, вам знадобиться поєднання візуалізації та мережевих метрик-показників у вашому власному проєкті, тому ми рекомендуємо цю статтю як додаток до цього попереднього уроку Programming Historian.
Пререквізити
Цей урок передбачає, що у вас є:
базове знайомство з мережами та/або ви попередньо прочитали "Від герменевтики до даних до мереж: вилучення даних і мережева візуалізація історичних джерел" Мартіна Дюрінґа тут, на Programming Historian;
встановлено Python 3, а не Python 2 (якщо вам потрібна допомога з інсталяцією Python 3, перегляньте "Посібник автостопом по Python");
встановлено інсталятор пакетів
pip
.встановлено програмне забезпечення для візуалізації мереж Gephi
На комп’ютері можна одночасно інсталювати дві версії Python (2 і 3). Тож через це, під час доступу до Python 3 вам часто доведеться вказувати саме його, ввівши python3 і pip3 замість просто python і pip. Перегляньте навчальні посібники Programming Historian щодо встановлення Python і роботи з pip, щоб дізнатися більше.
Що можна дізнатися аналізуючи мережі?
Які загальні риси має структура мережі?
Хто є "важливими" людьми або хабами в мережі?
Чи можна виділити окремі підгрупи (спільноти) в мережі?
Цей урок допоможе вам відповісти на такі питання, як:
Мережі вже давно цікавлять дослідників у гуманітарних науках, але багато науковців в останніх дослідженнях перейшли від переважно якісного та метафоричного інтересу до зв’язків, до більш формального набору кількісних інструментів для вивчення "посередників", "хабів" і "взаємопов’язаних структур". Як зазначив соціолог Марк Ґрановеттер у своїй статті 1973 року "Сила слабких зв’язків", важливо не лише помітити, що дві людини були пов’язані одна з одною, але й врахувати такі фактори, як їхній структурний зв’язок з іншими людьми та чи були ці "інші люди" також пов’язані між собою. Оскільки навіть найбільш кмітливим науковцям без додаткових розрахунків важко зрозуміти, скажімо, загальну форму мережі (її мережеву "топологію") і визначити вершини, найбільш важливі для з’єднання груп, кількісний аналіз мереж пропонує вченим спосіб відносно плавного переходу між великомасштабним соціальним об’єктом ("графом") та індивідуальними особливостями людей і їх соціальних зв’язків.
Наш приклад: деякі міщани, які жили у Львові на зламі XVI-XVII ст.
Маґдебурзьке право міст Східної Європи (Львова зокрема) походить із Заходу, із німецьких земель. Одним із найвідоміших німецьких правових збірників часів Середньовіччя було "Саксонське зерцало", закони якого, за посередництвом праць Бартоломея Ґроїцького, частково вживалися в міських судах Львова. Один із таких законів передбачав обов’язкове опікунство (представництво) для жінки, неповнолітніх дітей та духовних осіб в суді. Опікуном дружини найчастіше виступав чоловік; вдови — близький родич; дітей — призначені заповідачем або магістратом рідні, побратими по цеху, сусіди; монахів чи кліру — світський провізор монастиря, церкви або інші особи. Представник міг бути призначений на певний період (наприклад, до повноліття чи наступного шлюбу) або для якоїсь конкретної справи (tutor ad rem). Досліджуючи книги протоколів уряду ради Львова періоду 1578-1604 рр., вдалося укласти вибірку учасників судових процесів (жінок, неповнолітніх осіб і духовенства) та їх представників. З допомогою цих даних спробуємо з’ясувати, які люди найчастіше ставали опікунами в обраний проміжок часу. Дані подані в оригіналі, латинською мовою.
Підготовка даних і встановлення NetworkX
Перш ніж розпочати цей урок, вам потрібно буде завантажити два файли, які разом складають набір мережевих даних. Файл lviv_network_nodes.csv - це список жителів ранньомодерного Львова (вершини), а файл lviv_network_edges.csv - список зв’язків між цими людьми (ребра або зв’язки). Щоб завантажити ці файли, просто натисніть на посилання правою кнопкою миші та виберіть "Зберегти посилання як…". Перш ніж продовжити, буде дуже корисно ознайомитися зі структурою набору даних. Щоб дізнатися більше про загальну структуру мережевих наборів даних, перегляньте цей урок. Відкривши файл за допомогою обраної програми, ви побачите, що кожен міщанин, в основному, ідентифікується за своїм іменем. Кожна вершина також має пов’язаний атрибут - стать. Ось декілька перших рядків:
Зауважте, що хоча стовпці не вибудовуються правильно, як це відбувається в електронній таблиці, коми все розділяють у відповідному порядку.
Коли ви відкриєте файл з "ребрами", ви побачите, що ми використовуємо імена з файлу вершин для ідентифікації вершин, з’єднаних кожним ребром. Ці ребра починаються у вихідній вершині та закінчуються у цільовій вершині. Хоча така термінологія стосується перш за все спрямованих мереж - таких, у яких напрямок зв’язка має значення, ми ж для опису наших даних будемо використовувати неспрямовану мережу: якщо особа А знає особу Б, то особа Б також повинна знати особу А. У спрямованих мережах відносини не обов’язково мають бути взаємними (особа A може надіслати лист B, не отримавши відповіді), але в неспрямованих мережах зв’язки завжди взаємні або симетричні. Оскільки нашою метою є розглянути мережу знайомств, а не, скажімо, мережу листування, неспрямований тип зв’язків підходить для цього найкраще. Такий тип мережі найкраще підходить для ситуації, коли розглядаються зв’язки, які відіграють однакову роль для обох сторін: кожен із двох друзів є другом один одному. Автор листів та адресат мають асиметричні стосунки, оскільки кожен виконує різну роль. Спрямовані та неспрямовані мережі можуть описуватись різними параметрами та відповідати на різні запитання, тому потрібно обрати ту, що найкраще відповідає типам зв’язків між даними та задачам дослідження. Ось перші кілька ребер у неспрямованій мережі жителів Львова:
Тепер, коли ви завантажили дані та подивилися, як вони структуровані, настав час почати працювати з цими даними в Python. Після встановлення Python і pip (див. попередні пререквізити вище), вам потрібно інсталювати NetworkX, ввівши це в командний рядок:
Нещодавно NetworkX оновлено до версії 3.0. Якщо у вас виникли проблеми з наведеним нижче кодом і ви раніше працювали з NetworkX, ви можете спробувати оновити наведений вище пакет за допомогою pip3 install networkx==3.0 —upgrade
.
І це все! Ви готові почати кодити!
Починаємо
Читання файлів, імпорт даних
Створіть новий текстовий файл із назвою lviv_network.py
у папці, де лежать файли даних (щоб дізнатися більше про встановлення та запуск Python, перегляньте цей урок). Для початку роботи, імпортуйте потрібні бібліотеки. Вам знадобляться три бібліотеки — та, яку ми щойно встановили, і дві вбудовані бібліотеки Python. Ви можете ввести:
Тепер ви можете дати команду програмі читати ваші .csv файли і отримувати дані, які вам потрібно. За іронією долі, для читання файлів і реорганізації даних переважно потрібен більш складний код, ніж той, що потрібен для функцій, які використовуються для аналізу мереж, тому, опанувавши перший блок, ви опануєте і наступні. Ось набір команд для відкриття та читання наших файлів lviv_network_nodes.csv та lviv_network_edges.csv:
Цей код виконує функції, подібні до тих, що описані в цьому уроці, але використовує модуль CSV для завантаження вершин і ребер. Далі ви зможете отримати більше інформації про вершини, але наразі вам потрібні дві складові: повний список вершин і список пар ребер (як кортежі вершин). Це форми, які NetworkX використовуватиме для створення "об’єкту графа", спеціального типу даних NetworkX, про який ви дізнаєтеся в наступному розділі.
На цьому етапі, перш ніж почати використовувати NetworkX, ви можете виконати деякі основні перевірки, щоб переконатися, що ваші дані завантажуються правильно за допомогою вбудованих функцій і методів Python. За допомогою команд
та
ви побачите, скільки вершин і ребер ви успішно завантажили в Python. Якщо ви бачите 150 вершин і 127 ребер, то у вас є всі необхідні дані.
Основи NetworkX: створення графа
Тепер у вас є дані у вигляді двох списків Python: списку вершин node_names
і списку ребер edge_names
. У NetworkX ви можете об’єднати ці два списки в один мережевий об’єкт, який пов’язує між собою вершини та ребра. Цей об’єкт називається Graph (граф), який також визначають як сукупність об’єктів із зв’язками між ними. Цей термін використовують посилаючись на один із загальних математичних термінів для позначення даних, представлених у вигляді вершин, поєднаних ребрами.
Примітка: цей термін не означає початку генерації зображень чи графіків, а використовується тут суто для позначення математичного об’єкта
Спочатку ви повинні створити об’єкт Graph за допомогою такої команди:
Це створить новий порожній об’єкт Graph, G. Тепер ви можете додати свої списки вершин і ребер так:
Це один із кількох способів додавання даних до мережевого об’єкта. Ви можете переглянути документацію NetworkX, щоб отримати інформацію про додавання зважених ребер або додавання вершин і ребер одне за одним.
Зрештою, ви можете отримати основну інформацію про свою щойно створену мережу просто вивівши опис графа.
Результат має виглядати так:
Це швидкий спосіб отримати загальну інформацію про ваш граф, але, як ви дізнаєтесь у наступних розділах, це лише верхівка айсбергу того, що NetworkX може розповісти вам про ваші дані. Зауважте, що кількість ребер зменшилась - це через те, що ми маємо рядки, які повторюються, вершини-джерела та цільової вершини, однак з різними типами зв’язків, деякі з яких ми наразі не враховуємо.
Підсумовуючи, на даний момент ваш скрипт коду виглядатиме так:
Досі ви зчитували дані вершин і ребер у Python із файлів .csv, а потім підраховували ці вершини та ребра. Після цього ви створили об’єкт Graph за допомогою NetworkX і завантажили свої дані в цей об’єкт.
Додавання атрибутів
Для NetworkX об’єкт Graph — це одний великий об’єкт (ваша мережа), що складається з двох видів менших об’єктів (ваших вершин і ребер). Досі ви завантажували лише вершини та ребра (як пари вершин), але NetworkX дозволяє додавати атрибути до вершин та/чи ребер, надаючи більше інформації про кожен із них. Пізніше в цьому уроці ви запустите функції для обрахунку метрик та додасте деякі результати назад до Graph як атрибути. Наразі давайте переконаємося, що ваш Graph містить усі атрибути, які зараз є в нашому CSV-файлі.
Повернемося до двох списків, які ми створити на початку: nodereader та edgereader. У першому містяться всі рядки з файлу lviv_network_nodes.csv
, включно з міткою статі, а другий - всі рядки з файлу lviv_network_edges.csv
, в тому числі і мітки для позначення типу зв’язка. Тепер потрібно додати ці мітки до нашого графа. Є кілька способів зробити це, але NetworkX надає дві зручні функції для додавання атрибутів до всіх вершин або ребер Graph одночасно: nx.set_node_attributes()
і nx.set_edge_attributes()
. Але щоб використовувати ці функції, потрібно перетворити списки nodereader та edgereader у формат словників Python, що описують пари "ключ-значення". Потрібно отримати один словник, де ключами будуть назви вершин, а мітки статі (власне, атрибути, які хочемо додати) - значеннями, а другий словник - де ключами будуть пари назв вершин (ребра), а мітки для позначення типу взаємозв’язка - значеннями. Перше, що вам потрібно зробити — це створити 2 порожні словники, використовуючи фігурні дужки:
Тепер ми можемо прокрутити наш список вершин та ребер і додати відповідні елементи до кожного словника. Ми робимо це, знаючи заздалегідь позицію або індекс кожного атрибута. Оскільки наш файл lviv_network_nodes.csv
добре організований, ми знаємо, що ім’я людини завжди буде першим у списку з індексом 0, (оскільки в Python ви завжди починаєте підрахунок з 0), а стать людини буде індексована 1. Аналогічні міркування стосуються і файлу lviv_network_edges.csv
. Тому ми можемо будувати наші словники так:
Тепер у вас є набір словників, які можна використовувати для додавання атрибутів до вершин у вашому об’єкті Graph. Функції set_node_attributes
та set_edge_attributes
використовують три параметри: граф, до якого ви додаєте атрибут, словник пар ідентифікатор-атрибут та ім’я нового атрибута. Код для додавання ваших шести атрибутів виглядає так:
Тепер усі вершини графа мають атрибут статі, а ребра - атрибут типу зв’язку, і в будь-який момент можна перевірити цю інформацію для потрібного ребра чи вершиною. Наприклад, можна отримати статі людей у мережі, які репрезентовані вершинами, прокрутивши їх список і отримавши доступ до атрибута статі, ось так:
За допомогою цієї команди можна вивести список вершин мережі (імена людей) та їх атрибути (стать):
Наведені вище кроки є звичайним методом додавання атрибутів до вершин, які ви повторно використовуватимете пізніше в уроці. Ось підсумок кодового блоку з цього розділу:
Тепер ви дізналися, як створити об’єкт Graph і додати до нього атрибути. У наступному розділі ви дізнаєтесь про різні метрики, доступні в NetworkX, і про те, як до них отримати доступ. Але розслабтеся, тепер ви вивчили основну частину коду, який вам знадобиться для решти уроку!
Метрики, доступні в NetworkX
Коли ви починаєте працювати над новим набором даних, доцільно отримати загальне уявлення про дані. Перший крок, описаний вище, полягає у тому, щоб просто відкрити файли та подивитися, що всередині. Оскільки це мережа, ви знаєте, що там будуть вершини та межі, але скільки саме кожного з них? Яка інформація додається до кожної вершини або ребра?
У нашому випадку є 114 ребер і 149 вершин. Ці ребра не мають напрямків (тобто між людьми є симетричний зв’язок), однак характеризуються типом зв’язку. Для кожної вершини ми знаємо стать особи, що їй відповідає.
Ці деталі підказують, який підхід до аналізу даних варто обрати: якщо є надто мало вершин (скажімо, 15), то мережевий аналіз стає менш доцільним, аніж візуальний аналіз графа чи текстове представлення переліку вершин та ребер. Якщо є дуже велика кількість вузлів та зв’язків між ними (скажімо, 15 мільйонів), та можна почати з аналізу підмножини або ж розраховувати на значно більші комп’ютерні потужності.
Властивості мережі також керують вашим аналізом. Оскільки ця мережа неспрямована, ваш аналіз повинен використовувати метрики, які вимагають симетричних країв між вершинами. Наприклад, ви можете визначити, до яких спільнот потрапляють люди, але ви не можете визначити напрямкові маршрути, якими інформація може протікати в мережі (для цього вам потрібна спрямована мережа). Використовуючи симетричні ненаправлені зв’язки в цьому випадку, ви зможете знайти підспільноти та людей, які є важливими для цих спільнот, процес, який був би складнішим (хоча все ще можливим) із спрямованою мережею. NetworkX дозволяє виконувати більшість аналізів, які ви можете собі уявити, але ви повинні розуміти можливості свого набору даних і розуміти, що деякі алгоритми NetworkX більше підходять, ніж інші.
Форма мережі
Побачивши, як виглядає набір даних, важливо побачити, як виглядає мережа. Це різні речі. Набір даних — це абстрактне представлення того, якими є припущені зв’язки між об’єктами; мережа є конкретною реалізацією цих припущень. Мережа, принаймні в цьому контексті, — це те, як комп’ютер читає з’єднання, які ви закодували в наборі даних. Мережа має топологію або сполучну форму, яка може бути централізованою або децентралізованою; щільною або небагатою на зв’язки (рідкою); циклічною або лінійною. Водночас набір даних її не має, поза структурою таблиці, у якій він записаний.
Форма мережі та основні властивості дадуть вам зрозуміти, з чим ви працюєте та які аналізи здаються доцільними. Ви вже знаєте кількість вершин і ребер, але як "виглядає" мережа? Чи групуються вершини разом, чи вони однаково розподілені? Чи є складні структури, чи кожна вершина розташована вздовж прямої лінії?
Наведена нижче візуалізація, створена в інструменті візуалізації мережі Gephi, дасть вам уявлення про топологію цієї мережі. Ви можете створити подібний граф у Palladio, дотримуючись цього уроку.
Існує багато способів візуалізації мережі, і cиловий алгоритм візуалізації графів, прикладом якого є зображення вище, є одним з найпоширеніших. Силовий алгоритм візуалізації графів намагається знайти оптимальне розміщення для вершин за допомогою розрахунку, заснованого на натягу пружин у законі Гука, який для менших графів часто створює чіткі, легкі для читання візуалізації. Візуалізація, презентована вище, показує вам, що є декілька великих компонент з’єднаних вершин та більше маленьких компонентів лише з одним або двома з’єднаннями по краях. Це досить поширена структура мережі. Знання того, що в мережі є кілька компонентів, обмежить обчислення, які ви захочете виконати в ній. Відображаючи кількість з’єднань (відому як степінь, див. нижче) як розмір вершин, візуалізація також показує, що є кілька вершин із великою кількістю з’єднань, які утримують центральний компонент пов’язаним разом. Ці великі вершини відомі як хаби, і той факт, що вони тут так чітко з’являються, дає вам підказку про те, що ви знайдете, вимірявши центральність у наступному розділі.
Візуалізація, однак, має обмежені можливості. Чим більше мереж ви опрацюєте, тим більше усвідомите, що більшість з них здаються настільки схожими, що важко відрізнити одну від іншої. Кількісні показники дозволяють відрізняти мережі, дізнаватися про їхні топології та перетворювати нагромадження вершин і ребер на те, з чого можна навчитися.
Хорошим показником для початку є щільність мережі. Це просто співвідношення фактичних ребер у мережі до всіх можливих ребер у мережі. У ненаправленій мережі, як ця, між будь-якими двома вершинами може бути одне ребро, але, як ви бачили на візуалізації, насправді присутні лише деякі з цих можливих ребер. Щільність мережі дає змогу швидко зрозуміти, наскільки тісно зв’язана ваша мережа.
І добра новина полягає в тому, що багато з цих показників потребують простих однорядкових команд у Python. З цього моменту ви можете продовжувати будувати блок коду з попередніх розділів. Вам не потрібно видаляти нічого, що ви вже ввели, і оскільки ви створили свій мережевий об’єкт G
у кодовому блоці вище, усі метрики з цього моменту мають працювати правильно.
Ви можете обчислити щільність мережі, запустивши nx.density(G)
. Однак найкращий спосіб зробити це — зберегти свою метрику в змінній для подальшого використання та надрукувати цю змінну так:
Результатом щільності є число, тож це те, що ви побачите, коли надрукуєте значення. У цьому випадку щільність нашої мережі становить приблизно 0.0103. За шкалою від 0 до 1 це не дуже щільна мережа, яка відповідає тому, що ви бачите у візуалізації. 0 означатиме, що зв’язків немає взагалі, а 1 вказуватиме на наявність усіх можливих ребер (ідеально підключена мережа): наша мережа знаходиться на нижній частині цієї шкали, але все ще далека від 0.
Вимірювання найкоротшого шляху дещо складніше. Він обчислює найкоротший можливий ряд вершин і ребер, які стоять між будь-якими двома вершинами, що важко побачити у візуалізаціях великих мереж. Ця міра, по суті, полягає в пошуку друзів друзів — якщо моя мати знає когось, кого я не знаю, то мама є найкоротшим шляхом між мною та цією людиною.
Щоб обчислити найкоротший шлях, вам потрібно буде передати кілька вхідних змінних (інформацію, яку ви надаєте функції Python): весь граф, вихідну вершину і цільову вершину. Давайте знайдемо найкоротший шлях між Agnes Ganschornowa [Аґнес Ґаншорнова] і Abraam Dawidowicz Judaeus [Абрам Давидович Єврей]. Оскільки ми використовували імена для унікальної ідентифікації наших вершин у мережі, ви можете отримати доступ до цих вершин (як джерело та ціль вашого шляху), використовуючи безпосередньо імена.
Залежно від розміру вашої мережі обчислення може зайняти деякий час, оскільки Python спочатку знаходить усі можливі шляхи, а потім вибирає найкоротший. Результатом shortest_path
буде список вершин, який включає "джерело" (Agnes Ganschornowa), "ціль" (Abraam Dawidowicz Judaeus) і вершини між ними. У цьому випадку ми бачимо, що Paulus Kraus Ostiarius [Павло Краус Одвірний] знаходиться на найкоротшому шляху між ними. Оскільки Paulus Kraus Ostiarius також є центром (див. степінь центральності нижче) з багатьма зв’язками, ми можемо припустити, що кілька найкоротших шляхів проходять через нього як посередника. Що це може сказати про важливість Paulus Kraus Ostiarius для їхньої соціальної мережі?
Python містить багато інструментів, які обчислюють найкоротші шляхи. Є функції для визначення довжини найкоротших шляхів, для всіх найкоротших шляхів, а також для того, чи існує шлях взагалі в документації. Ви можете використати окрему функцію, щоб дізнатися довжину шляху Agnes-Abraam, який ми щойно розрахували, або ви можете просто взяти довжину списку мінус одиницю, ось так:
Існує багато мережевих показників, отриманих із довжини найкоротшого шляху. Одним із таких заходів є діаметр, який є найдовшим із усіх найкоротших шляхів. Після обчислення всіх найкоротших шляхів між кожною можливою парою вершин у мережі діаметр є довжиною шляху між двома найвіддаленішими вершинами. Цей показник розроблений, щоб дати вам уявлення про загальний розмір мережі, відстань від одного кінця мережі до іншого.
Діаметр використовує просту команду: nx.diameter(G)
. Однак виконання цієї команди на нашому графі призведе до повідомлення про помилку, що граф «незв’язний». Це просто означає, що ваш граф, як ви вже бачили, має більше ніж одну компоненту. Оскільки деякі вершини не мають жодного шляху до інших, неможливо знайти всі найкоротші шляхи. Погляньте ще раз на візуалізацію вашого графа:
Оскільки немає доступного шляху між вершинами одного компонента та вершинами іншого, nx.diameter()
повертає помилку "незв’язний". Ви можете виправити це, спершу з’ясувавши, чи ваш граф "з’єднаний" (тобто одна компонента зв’язності), і, якщо граф не з’єднаний, знайдіть найбільший компонент і обчисліть діаметр лише для цього компонента. Ось код:
Оскільки ми взяли найбільший компонент, можна припустити, що для інших компонентів немає більшого діаметру. Таким чином, ця цифра є гарним замінником діаметра всього графа. Діаметр мережі найбільшого компонента цієї мережі дорівнює 4: існує довжина шляху 4 між двома найбільш віддаленими вершинами в мережі. На відміну від щільності, яка змінюється від 0 до 1, за одним лише цим числом важко визначити, чи 4 є великим чи малим діаметром. Для деяких глобальних показників найкраще порівняти їх із мережами подібного розміру та форми.
Остаточний структурний розрахунок, який ви зробите в цій мережі, стосується концепції тріадичного замикання. Тріадичне замикання припускає, що якщо дві людини знають одну людину, вони, швидше за все, знають один одного. Кількість цих замкнутих трикутників у мережі можна використовувати для пошуку кластерів і спільнот індивідуумів, які знають один одного досить добре.
Один із способів вимірювання тріадного замикання називається коефіцієнтом кластеризації через цю тенденцію до кластеризації, але міра структурної мережі, яку ви дізнаєтеся, відома як транзитивність. Транзитивність — це відношення кількості наявних трикутників до кількості всіх можливих трикутників. Можливий трикутник існує, коли одна людина знає двох людей. Отже, транзитивність, як і щільність, виражає, наскільки взаємопов’язаний граф у термінах співвідношення фактичних зв’язків до можливих. Пам’ятайте, такі вимірювання, як транзитивність і щільність, стосуються ймовірності, а не достовірності. Усі виходи вашого сценарію Python необхідно інтерпретувати, як і будь-який інший об’єкт дослідження. Транзитивність дає вам спосіб думати про всі зв’язки у вашому графі, які можуть існувати, але зараз їх немає.
Ви можете обчислити транзитивність в одному рядку так само, як ви обчислили щільність:
Так само, як і щільність, транзитивність змінюється від 0 до 1, і ви бачите, що транзитивність мережі становить 0. Це означає, що або наші дані неповні та не відображають усіх можливих стосунків серед зрізу суспільства, що ми досліджуємо або що ці дані репрезентують специфічні групи з’єднані не дружніми стосунками, а радше через торгівлю чи послуги.
Центральність
Отримавши деякі базові показники всієї структури мережі, наступним кроком буде визначити, які вершини є найважливішими у вашій мережі. У мережевому аналізі показники важливості вершини називаються показниками центральності. Тому що є багато способів підійти до питання "Які вершини є найважливішими?" існує багато різних способів обчислення центральності. Тут ви дізнаєтесь про три найпоширеніші міри центральності: степінь, центральність за посередництвом та центральність власного вектора.
Степінь — найпростіший і найпоширеніший спосіб пошуку важливих вузлів. Степінь вершини — це сума його ребер. Якщо вершина має три лінії, що проходять від нього до інших вершин, його степінь дорівнює трійці. П’ять ребер, його степінь — п’ять. Це насправді так просто. Оскільки кожне з цих ребер завжди матиме вершину на іншому кінці, ви можете подумати про степінь як про кількість людей, з якими дана особа безпосередньо пов’язана. Вершини з найвищим степенем у соціальній мережі – це люди, які знають найбільше людей. Ці вузли часто називають концентраторами, і обчислення степеня є найшвидшим способом ідентифікації концентраторів.
Розрахунок центральності для кожної вершини в NetworkX не такий простий, як метрики для всієї мережі, наведені вище, але він все одно передбачає однорядкові команди. Усі команди центральності, які ви дізнаєтесь у цьому розділі, створюють словники, у яких ключі є вершинами, а значення – мірами центральності. Це означає, що їх можна знову додати у вашу мережу як атрибут вершини, як ви зробили в попередньому розділі. Почніть з обчислення степеня та додавання його як атрибута до вашої мережі.
Ви щойно запустили метод G.degree()
для повного списку вершин у вашій мережі (G.nodes())
. Оскільки ви додали його як атрибут, тепер ви можете побачити степінь Paulus Kraus Ostiarius разом з іншою його інформацією, якщо ви отримаєте прямий доступ до його вершини:
Але ці результати корисні не тільки для додавання атрибутів до об’єкта Graph. Оскільки ви вже використовуєте Python, ви можете сортувати та порівнювати їх. Ви можете використовувати вбудовану функцію sorted()
, щоб відсортувати словник за його ключами або значеннями та знайти перші двадцять вершин, упорядкованих за степенем. Для цього вам знадобиться використати itemgetter
, який ми імпортували на початку підручника. Використовуючи sorted
і itemgetter
, ви можете сортувати словник степенів таким чином:
Тут багато чого відбувається за лаштунками, але просто зосередьтеся на трьох вхідних змінних, які ви надали sorted()
. По-перше, це словник, degree_dict.items()
, який потрібно відсортувати. Друге – це те, за чим сортувати: у цьому випадку елемент "1" є другим елементом у парі або значенням вашого словника. Нарешті, ви вказуєте sorted()
діяти у зворотному порядку, щоб вершини з найвищим степенем були першими в списку, що є результатом перетворень. Після того як ви створили цей відсортований список, ви можете прокрутити його та використати метод "відокремлення частини списку"3, щоб отримати лише перші 20 вершин:
Як бачите, степінь Paulus Kraus Ostiarius - 23, що є відносно високим для цієї мережі. Але виведення цієї інформації про рейтинг ілюструє обмеження степеня як міри центральності. Можливо, вам не знадобилася мережа NetworkX, щоб сказати вам, що Paulus Kraus Ostiarius, був важливим. Більшість соціальних мереж матимуть лише кілька вершин дуже високого степеня, а решта – схожі, набагато нижчого степеня. Степінь може розповісти вам про найбільші центри, але не може сказати вам більше про решту вершин. І в багатьох випадках ті центри, про які вам розповідає (наприклад, Paulus Kraus Ostiarius або Adamus Kalinowski), не викликають особливого подиву. У цьому випадку майже всі хаби є важливими фігурами.
На щастя, існують інші показники центральності, які можуть розповісти вам не лише про хаби. Центральність власного вектора — це свого роду розширення степеня — воно розглядає комбінацію ребер вершин та ребер сусідніх вершин. Центральність власного вектора враховує чи ця вершина є хабом, як і до скількох інших хабів вона з’єднана. Він обчислюється як значення від 0 до 1: чим ближче до одиниці, тим більша центральність. Центральність власного вектора важлива для того, аби знати які вершини якнайшвидше передадуть інформацію всім іншим вершинам. Якщо ви знаєте багато людей із хорошими зв’язками, ви можете поширювати повідомлення дуже ефективно. Якщо ви користувалися Google, то ви вже дещо знайомі з центральністю власного вектора. Їхній алгоритм PageRank використовує розширення цієї формули, щоб визначити, які веб-сторінки потрапляють у верхню частину результатів пошуку.
Центральність за посередництвом дещо відрізняється від двох інших мір тим, що вона не зважає на кількість ребер будь-якої вершини або набору вершин. Центральність за посередництвом розглядає всі найкоротші шляхи, які проходять через певну вершину (див. вище). Щоб зробити це, потрібно спочатку обчислити всі можливі найкоротші шляхи у вашій мережі, тому майте на увазі, що обчислення центральності за власним вектором між ними займе більше часу, ніж інші показники центральності (але це не буде проблемою в наборі даних такого розміру). Центральність за посередництвом, яка також виражається за шкалою від 0 до 1, досить хороша для пошуку вершин, які з’єднують дві інші частини мережі. Якщо певна сутність єдине, що з’єднує два кластери, усі зв’язки між цими кластерами мають проходити через цю сутність. На відміну від хабу, цей вид вершин часто називають брокером. Центральність за посередництвом — це не єдиний спосіб знайти посередництво (і інші методи є більш систематичними), але це швидкий спосіб дати вам зрозуміти, які вершини важливі не тому, що вони самі мають багато зв’язків, а тому, що вони знаходяться між групами, даючи підключення та згуртованість мережі.
Ці два показники центральності навіть простіше виконувати, ніж степінь — їм не потрібно передавати список вершин, лише граф G
. Ви можете запустити їх за допомогою цих функцій:
Ви можете відсортувати центральність за посередництвом (або власний вектор), змінивши назви змінних у коді сортування вище, як:
Ви помітите, що багато, але не всі, вершини з високим степенем також мають високу центральність за посередництвом. Насправді, центральність за посередництвом виводить двох Agnes Ganschornowa olim Joannis Ganschorn secund. nupt. vidua [Аґнес Ґаншорнова, покійного Йоана Ґаншорна в другому шлюбі, вдова] та Anna Lucae Woinar cv. L. conj. [Анна, Луки Войнара, міщанина львівського, дружина] чия важливість була прихована на основі показника степеня центральності. Перевага виконання цих обчислень у Python полягає в тому, що ви можете швидко порівняти два набори метрик. Якщо ви хочете знати, яка із вершин з високою центральністю за посередництвом мала низький степінь? Тобто: які вершини несподівано виявляться із високим значенням центральності за посередництвом? Ви можете використовувати комбінацію впорядкованих списків, наведених вище:
На основі цих результатів ви можете переконатися, що деякі люди, як-от Agnes Ganschornowa olim Joannis Ganschorn secund. nupt. vidua та Anna Lucae Woinar cv. L. conj., мають високу центральність за посередництвом, але низький степінь. Це могло означати, що ці жінки були важливими вершинами-брокерами, які з’єднували різнорідні частини графа. Ви також можете дізнатися несподівані речі про людей, яких ви вже знаєте — у цьому списку ви можете побачити, що Anna Lucae Woinar cv. L. conj. має нижчий степінь центральності, ніж Stanislaus Anserinus [Станіслав Ансерін], але вищу центральність за посередництвом. Тобто просто знати більше людей — це ще не все.
Це лише частина того, що можна зробити з мережевими показниками в Python. NetworkX пропонує десятки функцій і заходів для використання в різних комбінаціях, і ви можете використовувати Python для розширення цих заходів майже необмеженими способами. Мова програмування, як-от Python або R, надасть вам гнучкість у дослідженні вашої мережі за допомогою обчислень у спосіб, яким не можуть скористатися інші інтерфейси, дозволяючи поєднувати та порівнювати статистичні результати вашої мережі з іншими атрибутами ваших даних (наприклад, тип зв’язку, який ви додали до мережі на початку цього уроку!).
Розширений NetworkX: Виявлення спільноти за допомогою модулярності
Інша важлива особливість, яку можна проаналізувати за допомогою мереж, це те, які підгрупи або спільноти входять до більшої соціальної структури. Чи є ваша мережа однією великою щасливою родиною, де всі знають усіх? Або це сукупність менших підгруп, які з’єднані лише одним або двома посередниками? Методи виявлення спільнот у мережах дають змогу відповісти на ці запитання. Існує багато способів обчислення спільнот, клік і кластерів у вашій мережі, але найпопулярнішим наразі є метод модулярності. Модулярність — це міра відносної щільності у вашій мережі: спільнота (яка називається модулем або класом модулярності) має високу щільність відносно інших вершин у своєму модулі, але низьку щільність щодо вершин поза її межами. Модулярність дає вам загальну оцінку того, наскільки розбіжна ваша мережа, і цю оцінку можна використовувати для розділення мережі та перегляду окремих спільнот.
Дуже щільні мережі часто важче розділити на окремі класи. На щастя, як ви з’ясували раніше, ця мережа є не така щільна. Фактичних з’єднань не так багато, як можливих з’єднань, і є кілька повністю від’єднаних компонентів. Варто розділити цю небагату на зв’язки мережу на модулі і перевірити, чи має результат історичний та аналітичний сенс.
Виявлення спільноти та розділення в NetworkX вимагає трохи більше налаштувань, ніж деякі інші показники. Є деякі вбудовані підходи до виявлення спільноти (наприклад, мінімальне скорочення, але модулярність не включена в NetworkX). На щастя, є додатковий модуль python, який ви можете використовувати з NetworkX, який ви вже встановили та імпортували на початку цього уроку. Ви можете прочитати повну документацію щодо всіх функцій, які він пропонує, але для більшості цілей виявлення спільноти вам знадобиться лише best_partition()
:
Метод greedy_modularity_communities()
намагається визначити кількість спільнот, відповідних для графа, і групує всі вершини в підмножини на основі цих спільнот. На відміну від центральних функцій, наведений вище код не створить словник. Замість цього він створює список спеціальних "заморожених" об’єктів (подібних до списків). Для кожної групи є один набір, і набори містять імена людей у кожній групі. Щоб додати цю інформацію до вашої мережі вже відомим способом, ви повинні спочатку створити словник, який позначатиме кожну особу числовим значенням для групи, до якої вона належить:
Використання центральності власного вектора як рейтингу може дати вам уявлення про важливих людей у цьому класі модулярності. Трохи покопавшись, ми можемо виявити, що існують причини (жінки звертались за послугами до Paulus Kraus Ostiarius аби він представляв їх у суді), які об’єднують цю групу людей. Це свідчить про те, що модулярність, ймовірно, працює належним чином.
У менших мережах, подібних до цієї, звичайним завданням є пошук і перелік усіх класів модулярності та їхніх членів. Ви можете зробити це, пройшовшись по списку communities
:
Зауважте, що в наведеному вище коді ви відфільтровуєте будь-які класи модулярності з двома або меншою кількістю вершин у рядку, якщо len(c) > 2
. З візуалізації ви пам’ятаєте, що було багато маленьких компонентів мережі лише з двома вершинами. Модулярність знайде ці компоненти та розглядатиме їх як окремі класи (оскільки вони не пов’язані ні з чим іншим). Відфільтрувавши їх, ви отримаєте краще уявлення про більші класи модулярності в головному компоненті мережі.
Працюючи лише з NetworkX, ви далеко зайдете, і ви зможете дізнатися багато про класи модулярності, просто працюючи безпосередньо з даними. Але ви майже завжди захочете візуалізувати свої дані (і, можливо, виразити модулярність у вигляді кольору вершини). У наступному розділі ви дізнаєтеся, як експортувати дані NetworkX для використання в інших програмах.
Експорт даних
NetworkX підтримує дуже велику кількість форматів файлів для експорту даних. Якщо ви хочете експортувати відкритий текстовий список ребер для завантаження в Palladio, для цього є зручна обгортка. Часто в Six Degrees of Francis Bacon експортують дані NetworkX у спеціалізований формат JSON D3 для візуалізації в браузері. Ви навіть можете експортувати свій граф як Pandas датафрейм, якщо ви хочете запустити більш розширені статистичні операції. Існує багато варіантів, і якщо ви старанно додавали всі свої показники назад у свій об’єкт Graph як атрибути, усі ваші дані буде експортовано одним махом.
Більшість параметрів експорту працюють приблизно однаково, тому в цьому підручнику ви дізнаєтеся, як експортувати дані у формат GEXF Gephi. Експортувавши файл, ви можете завантажити його безпосередньо в Gephi для візуалізації.
Експорт даних часто виконується простою однорядковою командою. Все, що вам потрібно вибрати, це ім’я файлу. У цьому випадку ми будемо використовувати lviv_network.gexf
. Для експорту введіть:
Ось і все! Коли ви запускаєте свій сценарій Python, він автоматично розміщує новий файл GEXF у тому ж каталозі, що й ваш файл Python.
Нарис висновків
Опрацювавши та переглянувши масив мережевих показників у Python, ви тепер маєте докази, на основі яких можна висунути аргументи та зробити висновки щодо цієї мережі міщан у ранньомодерному Львові. Ви знаєте, наприклад, що мережа має відносно низьку щільність, що свідчить про слабкі зв’язки та/або неповні вихідні дані. Ви знаєте, що спільнота організована навколо кількох непропорційно великих центрів. Що ще корисніше, ви знаєте про жінок із відносно низьким степенем, як-от Agnes Ganschornowa olim Joannis Ganschorn secund. nupt. vidua та Anna Lucae Woinar cv. L. conj., які (внаслідок високої центральності між ними) могли діяти як брокери, з’єднуючи кілька груп. Нарешті ви дізналися, що мережа складається з декількох великих компонент та багатьох дуже маленьких. Завдяки метаданим, які ви додали до своєї мережі, у вас є інструменти для подальшого вивчення цих показників і потенційного пояснення деяких структурних особливостей, які ви ідентифікували.
Ми хочемо, щоб кожен із цих висновків спонукав до додаткових досліджень, і не був крапкою чи доказом. Аналіз мереж — це набір інструментів для постановки цільових запитань про структуру зв’язків у наборі даних, і NetworkX надає відносно простий інтерфейс для багатьох поширених методів і показників. Мережі — це корисний спосіб розширити ваше дослідження груп об’єктів, надаючи інформацію про структуру спільноти, і ми сподіваємося, що цей урок надихне вас використовувати ці показники для збагачення ваших власних досліджень і вивчення гнучкості мережевого аналізу за межами візуалізації.
Про авторів
Джон Ледд є запрошеним доцентом кафедри аналітики даних в Університеті Денісона, де він використовує гуманітарні підходи до аналізу даних і мереж, щоб поміркувати про довгі переплетені історії медіа та технологій, особливо в ранньомодерній літературі. Джессіка Отіс, фахівець із цифрових гуманітарних наук в університетських бібліотеках і доцент кафедри історії в Університеті Карнеґі-Меллона. Крістофер Воррен є доцентом англійської мови в Університеті Карнеґі-Меллона, де він викладає дослідження раннього модерну та керує дослідницькою групою факультету цифрових гуманітарних наук. Скотт Вайнґарт, історик науки та фахівець із цифрових гуманітарних наук в Університеті Карнеґі-Меллона.
Переклад українською: Орися Віра, PhD, викладач кафедри історії в Українському Католицькому Університеті. Гліб Солоджук, студент програми "ІТ та бізнес-аналітика" факультету прикладних наук в Українському Католицькому Університеті.
Переклад рецензували: Ірина Балагура, кандидат технічних наук, старший науковий співробітник відділу оптичних носіїв інформації Інституту проблем реєстрації інформації НАН України (Київ), запрошений дослідник Nottingham University Business School (Великобританія) Олеся Мриголод, кандидат технічних наук, старший науковий співробітник лабораторії статистичної фізики складних систем Інституту фізики конденсованих систем НАН України (Львів)
Рекомендоване цитування: Ледд, Джон; Отіс, Джессіка; Воррен, Крістофер та Вайнґарт, Скотт. "Дослідження та аналіз мереж за допомогою Python." Programming Historian, переклала Орися Віра та Гліб Солоджук, Посібник з цифрової історії, 2024. DOI: https://doi.org/10.69915/dh0010
Last updated