Grid technologies for social network analysis
This article deals with researching the ability of using Grid-technologies for solving problems of social networks analysis. One of the method of social analysis is implemented and experimental computations with the data from real online social networks were conducted. Determined pros and cons of ch...
Збережено в:
| Дата: | 2026 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2026
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1009 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| _version_ | 1867841442730213376 |
|---|---|
| author | Tkachenko, V.V. |
| author_facet | Tkachenko, V.V. |
| author_institution_txt_mv | [
{
"author": "V.V. Tkachenko",
"institution": "NTUU \"KPI\""
}
] |
| author_sort | Tkachenko, V.V. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2026-06-12T14:33:31Z |
| description | This article deals with researching the ability of using Grid-technologies for solving problems of social networks analysis. One of the method of social analysis is implemented and experimental computations with the data from real online social networks were conducted. Determined pros and cons of chosen method of solving task and ways of overcoming them offered.Problems in programming 2009; 1: 73-84 |
| first_indexed | 2026-06-13T01:00:10Z |
| format | Article |
| fulltext |
Прикладне програмне забезпечення
© В.В. Ткаченко , 2009
ISSN 1727-4907. Проблеми програмування. 2009. № 1 73
УДК 681.3
В.В. Ткаченко
ВИКОРИСТАННЯ ГРІД-ТЕХНОЛОГІЙ ДЛЯ АНАЛІЗУ
СОЦІАЛЬНИХ МЕРЕЖ
Розглянуто питання можливості та доцільності використання Grid-технологій для вирішення задачі
аналізу соціальних мереж. Реалізовано один з методів соціального аналізу та проведено
експериментальні обчислення на тестовій Grid системі з використанням соціальних даних з реальних
соціальних мереж. Визначено недоліки обраного методу розв’язання задачі та окреслено шляхи їх
подолання.
Вступ
Масове використання Інтернету та
природне прагнення людей до спілкування
та об’єднання у соціальні групи сприяло
створенню оперативних (онлайн) соціа-
льних сервісів. Соціальний сервіс – це Ін-
тернет-сервіс, шо надає послуги з утво-
рення та підтримки соціальних спільнот і
мереж. Тобто, з позиції соціології, люди,
здійснюючи різні комунікації у цьому сер-
вісі утворюють соціальну мережу, що в
кінці-кінців може охопити весь світ (якщо
припустити, що абсолютно ізольованих
груп людей не буває).
Соціальна мережа – це спільнота
людей, об’єднаних однаковими інтере-
сами, уподобаннями, або тих, що мають
інші причини для безпосереднього спілку-
вання між собою. Сучасні Інтернет-сервіси
забезпечують користувачів усіма можли-
вими інструментами для спілкування одне
з одним – відео, чати, зображення, музика,
блоги, форуми тощо.
Для бізнесу соціальні мережі ви-
ступають новим каналом комунікації із
споживачем, та інструментом дослідження
уподобань аудиторії. У щорічній доповіді
Gartner Emerging Technologies Hype Cycle
[1] представлені досягнення в області ін-
тернету та програмного забезпечення, які
вплинуть на розвиток бізнесу в найближчі
10 років. В області Web 2.0 найбільш важ-
ливою технологією названий аналіз соціа-
льних мереж, що досягне своєї зрілості
менш ніж за два роки. Аналіз соціальних
мереж (у визначенні Gartner) – це викорис-
тання інформації та знань, зібраних з пер-
сональних ресурсів людей, з метою ви-
вчення цільових ринків, винесення бізнес-
рішень і створення команд виконавців
проектів. Тобто, задача аналізу мереж є
важливою не тільки для соціологів, але й
для вирішення задач більш ефективного
ведення бізнесу. Методи аналізу соціаль-
них мереж успішно застосовуються для
аналізу політичних угруповань [2], терро-
ристичних організацій [3], поширення ін-
фораціїї серед працівників компаній та ви-
значення реального положення посадовців.
Таких прикладів можно навести значно бі-
льше.
Зупинимось на задачі соціального
аналізу. Існує чотири підходи щодо аналізу
соціальних мереж [4]:
1. Структурний – акцентує увагу на
геометричній формі та інтенсивності взає-
модій (вазі ребер). Всі актори розгляда-
ються як вершини графа, які впливають на
конфігурацію ребер і інших акторів ме-
режі. Особлива увага приділяється взаєм-
ному розташуванню вершин, центрально-
сті, транзитивності взаємодій. Для інтер-
претації результатів у даному випадку ви-
користовуються структурні теорії і теорії
мережевого обміну.
2. Динамічний – увага акцентована
на змінах у мережевій структурі з ча-
сом. Вивчаються причини зникнення і по-
яви ребер мережі; зміни структури мережі
при зовнішніх діях; стаціонарні конфігура-
ції соціальної мережі.
3. Нормативний – вивчає рівень до-
віри між акторами, а також норми, правила
та санкції, які впливають на поведінку ак-
торів у соціальній мережі та процеси їх
взаємодій. У цьому випадку аналізуються
соціальні ролі, які пов'язані з даним ребром
мережі, наприклад, відношення керівника і
Прикладне програмне забезпечення
74
підлеглого, дружні або родинні зв'язки.
Комбінація індивідуальних і мережевих
ресурсів актора з нормами і правилами, що
діють в даній соціальній мережі, утворює
його «соціальний капітал».
4. Ресурсний – розглядає можливо-
сті акторів по залученню індивідуальних і
мережевих ресурсів для досягнення певної
мети і диференціює акторів, що знахо-
дяться в ідентичних структурних позиціях
соціальної мережі, за їх ресурсами. Як ін-
дивідуальні ресурси можуть виступати
знання, престиж, багатство, (етнічность),
стать (гендерна ідентичність). Під мереже-
вими ресурсами розуміються вплив, статус,
інформація, капітал.
Наступні аналітичні методи засто-
совуються у соціальному аналізі [4]:
1) методи теорії графів;
2) методи знаходження локальних
властивостей суб'єктів, методи визначення
еквівалентності акторів, включаючи їх
структурну еквівалентність;
3) блокові моделі і ролева алгебра;
4) аналіз діад і тріад;
5) імовірнісні моделі;
6) кореспондентський аналіз і то-
пологічні методи, що представляють ме-
режу як деякий симпліціальний комплекс.
Особливістю оперативних соціаль-
них мереж, як джерел соціальних даних є
те, що користувачі розширюють свої ме-
режі доволі швидко та без додаткових ви-
трат зі сторони соціального аналітика. Це
зумовлює великі розміри соціальних гра-
фів, на яких можуть здійснюватись
маcштабні дослідження різноманітних
властивостей соціальних мереж. Прибли-
зні розміри соціальних мереж наведено у
табл. 1.
У даній роботі розглядаються саме
оперативні соціальні мережі. Як задача,
яка буде реалізована з виконанням грід-
технологій, обрано задачу пошуку соціа-
льних ланцюгів між усіма соціальними
акторами у мережі
Існуючі системи для аналізу
соціальних мереж
На сьогоднішній день існує багато
систем аналізу соціальних даних, що ви-
користовуються здебільшого соціологами
для проведення досліджень: UCINET,
NetDraw, Pajek, Netminer, Visone, SNA/R,
StOCNET, Negopy, InFlow, GUESS,
NetworkX, prefuse, JUNG, BGL/Python та
інші. З детальним списком систем для
аналізу соціальних мереж можна ознайо-
митись на сайті міжнародної спільноти з
аналізу соціальних мереж ISNA [9] та в
огляді [10], а нині зупинимось на деяких з
них, які я намагалась застосовувати для
аналізу даних з оперативних соціальних
мереж. Однією з найвідоміших є UCINET
– комерційний продукт, що розроблюється
американською компанією Analytic
Technologies. Вона дозволяє здійснювати
аналіз соціальних мереж використовуючи
широкий спектр методів аналізу, експор-
тувати дані з найпопулярніших форматів,
інтегрується з системою візуалізації мереж
NetDraw. Одним з найголовніших обме-
жень є максимальний розмір акторів у ме-
Мережа
Кількість
акторів, тис
Кількість зв'язків, тис Джерело даних
MSN messenger 180 000 1 300 000 [5]
LinkedIn 22 000 Немає даних [6]
FaceBook 100 000 Немає даних [7]
Orkut 3 000 223 500 [8]
LiveJournal 5 000 77 500 [8]
Середня мережа блогів 4 400 5 000
[Liben-Nowell et al. 2005,
Backstrom et at. 2006]
Мережа цитувань серед
фізичних статей
31 350 [5]
Таблиця 1. Приблизні розміри деяких соціальних мереж
Прикладне програмне забезпечення
75
режі 32767, але й при обробці даних для
5,000 10,000 акторів виникають значні за-
тримки у роботі. Для обробки більших за
розмірів даних створена словенськими
розробниками Vladimir Batagelj та Andrej
Mrvar система Pajek [11]. Обробка великих
соціальних мереж досягається її кластери-
зацією на менші і застосовуванням адапто-
ваних алгоритмів.
Жоден з розглянутих автором про-
дуктів не дозволив у прийнятний час про-
аналізувати соціальну мережу з 2 000 000
акторів. Тому для зберігання такого (або
більше) об’єму даних та його аналізу має
бути розроблений інший продукт, що мав
би більш зручний та доступний для біль-
шої кількості користувачів інтерфейс. Зви-
чайно, створюваний продукт не дозволить
здійснити всі види соціального аналізу, але
оскільки «генераторами» соціальної ме-
режі є звичайні люди (не соціологи), то
зацікавлені у характеристиках мережі саме
вони. Тому акцент у системі буде зміщено
з повноти охоплення методів соціального
аналізу на можливість аналізу реальних
оперативних соціальних мереж та зручний
доступ до результатів.
Опис типової задачі аналізу
Основною задачею соціальних ме-
реж є підтримання існуючих та пошук но-
вих зв'язків між людьми. Тому велику
практичну цінність несе інформація про
довжину та склад соціального ланцюга між
двома акторами у мережі. Введемо насту-
пну термінологію для опису соціальних
графів:
1. Соціальний об'єкт (актор) –
структурний елемент соціальної мережі,
наприклад, людина, група людей, органі-
зація, країна і т.д.
2. Соціальний зв'язок (взаємозв'я-
зок) – будь-який акт взаємодії між соціа-
льними об'єктами, наприклад, товариство,
листування, цитування, коментування і
т.п.
3. Соціальний граф – граф, вуз-
лами якого є соціальні об'єкти, а ребрами
– соціальні зв'язки.
Розглянемо зміст цих понять на на-
ступному прикладі. Нехай тестова соціа-
льна мережа складається з шістьох акторів:
A, B, C, D, E та F. Відповідний соціальний
граф показано на рис. 1.
Рис. 1. Тестовий соціальний граф
Соціальний ланцюг між акторами F
та E складається з двох інших акторів:
A -> C. Зауважимо, що існує й інший, з
трьох акторів: A -> B -> C. Практична цін-
ність пошуку таких ланцюгів полягає у
встановленні контакту з якимось актором
через знайомства.
Найпростішим методом пошуку
всіх таких ланцюгів є простий перебір усіх
варіантів. Одним з способів здійснення
такого перебору є піднесення до степеня
матриці суміжності M. Так, щоб отримати
кількість ланцюгів довжиною 2 необхідно
піднести M до квадрата і отримане зна-
чення M2(i,j) буде вказувати на кількість
ланцюгів між акторами i та j (0 у випадку
їх відсутності), для Mn відповідно це зна-
чення буде вказувати на кількість ланцюгів
довжиною n-1.
Для нашого тестового графа мат-
риця інцидентності матиме вигляд:
ij A B C D E F
A 3 1 1 1 1 0
B 1 2 1 1 1 1
C 1 1 4 0 0 1
D 1 1 0 1 1 0
E 1 1 0 1 1 0
F 0 1 1 0 0 1
ij A B C D E F
A 0 1 1 0 0 1
B 1 0 1 0 0 0
C 1 1 0 1 1 0
D 0 0 1 0 0 0
E 0 0 1 0 0 0
F 1 0 0 0 0 0
Відповідно М2 =
Прикладне програмне забезпечення
76
Для прикладу, M2(A,E) = 1, що під-
тверджується наявністю зв'язків вершини
A з вершиною C і С з E.
Але, характер соціальних даних,
отриманих з оперативних соціальних ме-
реж такий, що соціальний граф розрідже-
ний, і формат зберігання даних у вигляді
матриць суміжності не є оптимальним, а
метод множення матриці суміжності також
не є оптимальним. Тому застосовується
модифікація описаного алгоритму.
Опис алгоритму
Для знаходження ланцюга соціаль-
них знайомств, застосовується доволі про-
стий та неефективний метод перебору всіх
варіантів ланцюгів (складність O(n2)), ха-
рактеристики якого будуть покращено за
рахунок використання розподілених об-
числень.
Представимо соціальний граф у ви-
гляді масиву множин об'єктів, що мають
зв'язок з даних об'єктом, тобто
SocGraph = [S1, S2, ... , Sn],
Si = < O1, O2, ... , Om > .
Отримання ланцюга соціальних
зв'язків 1-го порядку:
SocGraphi
2 = Union Si < intersect > Sj,
j = 0..N, j! = i .
На мові псевдокоду алгоритм має наступ-
ний вигляд:
for i:=1 to < кількість акторів > – 1 do
множ1 = отримати список друзів для
i-го актора
for j:= i+1 to < кількість акторів > do
множ2 = отримати список друзів
для j-го актора
if (перетин множ1 та множ2 не пус-
тий) then
Зберегти (i та j друзі)
else
Зберегти (i та j не друзі)
fi
od
od
У поточній реалізації алгоритму
розпаралелюванню підлягає зовнішній
цикл по i.
Для зменшення кількості варіантів
для перебору застосовуються наступні ев-
ристики:
• якщо актор не має друзів, то для
нього не шукаються ланцюги, він просто
ігнорується;
• якщо два актора вже є друзями, то
це не підтверджується ще раз;
• як потенційні друзі розглядаються
тільки актори з більшим ідентифікатором
(це випливає з симетричності матриці су-
міжностей для неорієнтованих графів,
якими здебільшого є соціальні).
Модель розпаралелювання та
Грід-платформа
Як схема обробки соціальних даних
застосовується модель MapReduce [12], що
складається з двох фаз Map (розподіл за-
дач) та Reduce (формування результату).
Зупинимось на кожній з них окремо.
• Фаза Map: вхідні дані (у нашому ви-
падку списки суміжності <V1,V2, ..., Vn>)
розподілюються поміж обчислювачів бло-
ками за k списками value = (Vi,Vj) і кожно-
му набору ставиться у відповідність ключ,
що складається з номерів відповідних вер-
шин key = (i,j).
Кожен обчислювач отримує вхідні
дані – пару <key,value> і виконує необ-
хідні операції над ними. Наступний його
крок полягає у формуванні проміжного
результату:
intermResult = <key, operation(value)>
і надсилання його на керуючий вузол, що
виконує процедуру об'єднання.
• Фаза Reduce: дана фаза полягає у
формуванні кінцевого результату з отри-
маних від обчислювачів проміжних, тобто
finalResult = ReduceOperation itermResulti .
У якості програмно-апаратної пла-
тформи для соціального аналізу доцільно
використати Грід. Такі спроби робились у
[13].
Грід або Грід-інфраструктура – це
розподілена програмно-апаратна комп’ю-
терна мережа з принципово новою органі-
зацією обчислень і керування потоками
Прикладне програмне забезпечення
77
завдань і даних. Така комп’ютерна інфра-
структура призначена для об’єднання об-
числювальних потужностей різноманітних
організацій. На основі технології Гріду
(Грід-технології) здійснюється інтегру-
вання регіональних і навіть національних
обчислювальних комп’ютерних інфра-
структур для створення об’єднаних інтер-
національних ресурсів, щоб розв’язувати
маштабні науково-технічні задачі. В Гріді
передбачено інтегрування великої кілько-
сті географічно віддаленних комп’ю-
терних ресурсів. У ідеальному випадку
користувачеві не потрібно знати, де
розміщено ресурси, які він використовує
(у цьому і є аналогія з мережою електро-
постачання).
Серед основних на даний час за-
вдань, розв’язуваних за допомогою Грід-
технологій, можна виділити:
• організацію ефективного викорис-
тання ресурсів для невеликих задач з залу-
ченням тимчасово простоюваних комп’ю-
терних ресурсів;
• розподілені суперобчислення, роз-
в’язки дуже великих задач, які вимагають
величезних процесорних ресурсів, пам’яті
тощо;
• обчислення з залученням великих об-
сягів географічно розподілених даних, на-
приклад, в метерелогії, астрономії, фізиці
високих енергій;
• колективні обчислення за участю ко-
ристувачів з різних організацій.
Більш детально з Грід-технологіями
можна ознайомитись у [14].
Основними вимогами до платформи
для аналізу є можливість реалізації запро-
понованої схеми розпаралелювання, вико-
ристання неспеціалізованних комп'ютерів
як обчислювачів, легкість конфігурування,
інтеграція з рішеннями для кешування да-
них. У якості програмної платформи об-
рано Gridgain [15], так як вона на відміну
від інших (Globus toolkit, GridWay,
UNICORE, Sun Grid Engine та інші) є най-
більш простою у використанні, що дозво-
ляє більш швидко реалізовувати необхідні
обчислення.
Gridgain – це Open Source Грід-пла-
тформа, що заснована на Java та підтримує
балансування навантаження й обробку
розподілених даних. Архітектура системи
на базі цієї платформи показана на рис. 2.
Рис. 2. Архітектура Grid-системи на базі
GridGain
Заснований на SPI (Service Provider
Interface – інтерфейс надання послуг) архі-
тектурі Gridgain дозволяє розширювати
функціональність без зміни ядра системи,
що робить можливою реалізацію нових
концепцій (у тому числі й призначених для
користувача) дуже простою. Балансування
навантаження має декілька стратегій у то-
му числі: Round Robin (за умовчанням),
адаптивне і прив'язане до даних (афінне)
балансування. Працюючи з великими об-
сягами даних необхідно уникати переси-
лки їх по мережі з вузла на вузол. Gridgain
надає наступну функціональність для оп-
тимізації роботи з великим обсягом даних
– афінний балансувальник навантаження,
що дозволяє прив'язувати завдання до об-
роблюваних даних і виконувати їх на тих
вузлах, де знаходяться дані.
GridGain працює за принципом ди-
намічного перерозподілу завдань ("Work
stealing") між вузлами гріда (передаючи їх
з переобтяжених вузлів у гріді на найменш
завантажені). Цей SPI так само як й інші
підтримує відмовостійке і кероване вико-
нання завдань на Грід. Початкова ідея
"Work stealing" ґрунтується на методі
fork/join, що запропонований у [16] та за-
планований у версії SE 7 платформи Java.
Ця функціональність може використовува-
тися для уникнення "зависання" завдань на
слабких вузлах.
Сегментація Гріда на групи, які пра-
Прикладне програмне забезпечення
78
цюють над своїми завданнями, дозволяє
при необхідності реалізувати концепцію
керуючих та обчислювальних вузлів. Збе-
реження проміжних результатів обчислень,
що необхідне при виконанні тривалих за-
вдань, дозволяє продовжити обчислення з
останньої "збереженої" крапки.
Платформа включає також насту-
пну функціональність:
• моніторинг: GridGain дозволяє отри-
мувати різну інформацію про вузли, таку
як використання пам'яті або процесора,
кількість виконуваних завдань на вузлі та
іншу;
• IOC(Inversion of control): GridGain
підтримує можливість загального доступу
до призначених для користувача ресурсів
(таких як JDBC з'єднання або Spring біни в
процесі виконання);
• контекст виконання завдання, що до-
зволяє підзадачам обмінюватися інформа-
цією.
GridGain інтегрується з багатьма
open source і комерційними продуктами,
такими як JUnit, ASPECTJ, Spring, JBoss &
JGroups, GlassFish, WebLogic, WebSphere,
Coherence, Mule, JXInsight та GigaSpaces.
Розглянемо основні концепції ство-
рення Грід-систем на базі GridGain та
спрощену послідовність виконання задачі
на Гріді (рис. 3)..
Рис. 3. Виконання підзадачі на вузлі при
централізованому доступі
Одиницею виконуваної задачі є
GridTask, який відповідальний за розподіл
бізнес логіки на декілька підзадач
(GridJob). Рішення як саме та в залежності
від яких параметрів розподіляти задачу на
підзадачі приймається кодується у методі
GridTask::map, вхідними параметрами яко-
го є параметри задачі та список доступних
вузлів, на яких буде виконуватись задача.
Даний метод викликається перед виконан-
ням задачі і результатом роботи його є
список підзадач, які необхідно виконати.
Далі Грід-система забезпечує передачу
підзадач на обчислювачі (крок 1 рис. 3),
отримання необхідних для вирішення під-
задач ресурсів, їх виконання (крок 2 і 3) та
повернення результатів обчислення підза-
дачі (крок 4) до вузла, який ініціював зада-
чу (керуючий вузол). Список результатів
передається у метод GridTask::reduce від-
повідної задачі, в якому результати
об’єднуються за заданим алгоритмом і фо-
рмується фактичний результат виконання
задачі.
Для більшої наочності розглянемо
обчислення простої та добре знайомої за-
дачі пошуку заданого тексту в деякій су-
купності текстових файлів. Задачею у да-
ному випадку буде пошук тесту, а вхід-
ними параметрами, сам текст та список
файлів. Ураховуючи кількість вузлів, спи-
сок файлів буде розподілений серед вузлів
і на вхід кожної поступить текст, який не-
обхідно знайти, та список файлів, за пошук
у яких цей вузол відповідальний. Доступ
до файлів, які в нашому випадку знахо-
дяться в якомусь хранилищі, може бути
здійсненним, наприклад, за протоколами
передачі даних HTTP, FTP, SFTP і т. п. Пі-
сля отримання файлів за списком та пошу-
ком у них, вузол формує результат вико-
нання підзадачі у вигляді списку файлів та
позицій тексту в них та надсилає на керу-
ючий вузол. Як результат отримаємо міс-
цезнаходження заданого тесту. Якщо по-
трібно буде знайти якийсь інший текст у
тому ж списку файлів, то немає необхідно-
сті завантажувати ці файли знову. В цьому
випадку доцільно використати ідеї кешу-
вання інформаціі, що у GridGain реалізу-
ється прив’язанним до даних розподілом
навантаження, яке вищеописано. Дана ідея
Прикладне програмне забезпечення
79
показана на рис. 4. При надходженні (крок
1) підзадачі на обчислювальний вузол, у
залежності від розміщення необхідних да-
них вона пересилається на потрібний вузол
(2 чи 3 на рис. 4). Далі, підзадача обчислю-
ється (крок 2) на визначеному вузлі та ре-
зультат передається (кроки 3-4) на керую-
чий вузол.
Рис. 4. Виконання підзадачі з прив’язаним
до даних розподілом навантаження
Таблиця 2. Склад тестового Гріда
Обчислювальні ресурси
Як обчислювальні ресурси у Грід-
системах можуть використовуватись як
звичайні комп’ютери, так і більш потужні
сервери, кластери та суперкомп’ютери.
Вузли можуть класифікуватися за різними
технічними параметрами і задачі розподі-
лятися за вузлами у залежності від її класу
(у GridGain існує вбудований спосіб оці-
нки можливостей вузлів –
GridLocalNodeBenchmark).
Тестовий Грід для дослідження задачі
складався з 5 вузлів, що мали приблизні
конфігурації наведені у таблиці 2 (варто
зазначити, що швидкість обміну даними з
сервером БД є величиною доволі нестабі-
льною і наведені виміри при передачі фай-
лу розміром 100Мб лише характеризують
клас мережі).
У Гріді все ж таки існує два центра-
лізовані елементи:
• керуючий вузол (macbook) – розпо-
діляє задачі серед обчислювачів, сама є
обчислювачем, вимірює час виконання
задачі;
Кодова назва Технічні характеристики,
CPU, RAM, OS, Net, JRE, GridGain
Швидкість обміну да-
ними з сервером БД,
100Mb
selena AMD Athlon 64 Processor 2800+ 1.83 GHz, 1 Gb,
Debian (2.6.18), UA-IX
JRE6, 2.1.0
Майже необмежена, бо і є
сервером БД
netcat AMD Athlon 64 Processor 2800+ 1.83 GHz, 1 Gb,
Debian (2.6.18), UA-IX
JRE6, 2.1.0
500KB/s
macbook Intel Core 2 Duo 1.83 GHz, 1.5 GB
Mac OS X 10.5.6, UA-IX
JRE5, 2.1.0
10MB/s
frontera Intel Core2 Duo CPU 2.33 GHz, 3 Gb
Debian (2.6.18), UA-IX
JRE6, 2.1.0
20KB/s
netsfera Intel Core2 Duo CPU 2.33 GHz, 1 Gb
Windows XP, UA-IX
JRE6, 2.1.o
10MB/s
Прикладне програмне забезпечення
80
• сервер баз даних (selena) – зберігає
соціальні дані та результати аналізу, най-
більш «вузьке» місце системи.
Схема мережевого зв’язку між вуз-
лами та інформаційні потоки показані на
рис. 5. Темніші лінії показують двосторон-
ні потоки обміну данними з сервером БД.
Як вищезазначено, платформа
GridGain має компонентну архітекту-
ру (компонентом є SPI) і за пошук
та об’єднання окремих вузлів у тополо-
гію відповідає Discovery SPI. Існує багато
цього SPI: Jgroups, Jms, Mail, Mule,
Coherence, Multicast та інші. Для
об’єднання тестового Гріда використову-
вався JGroups [17] тулкіт для здійснення
надійних мультикаст та TCP (Transmission
Control Protocol) коммунікацій між хоста-
ми у мережі. Хости, яким необхідно
об’єднатись, обмінюватись даними,
об’єднуються у групи. Політика додаван-
ня/видалення елементів у групі конфігуру-
ється. Одним з найпростіших варіантів є
задання списку IP (Internet protocol) адрес
інших учасників групи.
На рис. 6 показаний «відбиток» то-
пології Гріда на момент «випадання» з
нього 1-го вузла (netsfera) і на ньому вид-
но, що Грід складається з 4-х вузлів і має
сумарну кількість процесорів 7. Також на-
ведені деякі характеристики вузлів та їх
унікальні ідентифікаційні номери.
Рис. 5. Схема мережі та інформаційних потоків у тестовому Гріді
Рис. 6. Миттєвий «відбиток» топології Гріда на базі GridGain
Прикладне програмне забезпечення
81
Соціальні дані
Створювана система ставить на меті
аналіз реальних, а не змодельованих, соці-
альних мереж. На жаль, дані, що збирають-
ся популярними оперативними мережами є
закритими для вільного доступу, точніше
важкодоступними. Щодо створення стати-
чного образу мережі існує три підходи:
• прямий доступ до даних у внутріш-
ньому форматі сервісу – цей метод може
бути використаний лише за домовленністю
з власником сервісу;
• використовувати API для доступу до
інформації про користувача – ця можли-
вість інколи пропонується у деяких опера-
тивних сервісах і може мати деякі обме-
ження (необхідність авторизації, обмежен-
ня кількості запитів);
• "краулінг" – тобто простий обхід сто-
рінок користувачів мережі та їх синтаксич-
ний аналіз із метою отримання даних про
користувача, а в нашому випадку списку
його друзів.
Для тестування системи використовува-
лись дані з трьох популярних в Україні та
за кордоном сервісів, що пропонують ко-
ристувачам можливість об'єднання у соці-
альні мережі, а саме такі:
• український портал bigmir.net, що на-
дає серед інших сервісів можливість ство-
рення щоденників, фотоальбомів та ін.;
дані були отримані першим методом;
• LiveJournal (www.livejournal.com) –
віртуальна спільнота, в якій користувачі
можуть вести свої блоги;
• Orkut (www.orkut.com) соціальна ме-
режа створена компанією Google.
Дані для останніх двох отримані
з проекту збору соціальних даних з
оперативних мереж (табл. 3) [17].
Підсистема зберігання даних
Вибір підсистеми зберігання соціа-
льних даних залежить від характеру самих
даних, алгоритмів роботи з ними та спосо-
бу використання отриманих результатів.
На жаль, на сьогодні майже кожна з систем
для аналізу соціальних мереж та оператив-
них соціальних сервісів має свій внутрі-
шній формат зберігання даних. Враховую-
чи те, що дані соціальних мереж можуть
бути представлені у вигляді соціального
графа, і використовують модифікації фор-
матів для зберігання графів. Прикладами
таких форматів є:
• csv (comma separated values) – най-
простіший та найпоширеніший з форматів
для представлення табличних даних (будь-
який граф може буде представлено у ви-
гляді таблиці, де кожен рядок відображає
відношення між зазначеними у ньому дво-
ма вершинами);
• dot – використовується у системі ві-
зуалізації графів GraphViz;
• pajek – формат даних відомої систе-
ми аналізу та візулізації соціальних мереж
Pajek;
• dl – внутрішній формат системи
UCINET;
• XML подібні формати – NetML,
DyNetML.
У eSNA наразі реалізована підтрим-
ка двох форматів вхідних даних csv файли
та дані, що були попередньо експортовані
у внутрішню базу даних системи.
Дані про відношення між актора-
ми зберігаються у вигляді реляційної
табл. 4.
Таблиця 3. Характер даних, що використовувались для тестування
Параметр bigmir.net LiveJournal Orkut
Кількість акторів 2 148 838 5 284 457 3 072 441
Кількість
активних акторів
136 643 Немає даних Немає даних
Кількість зв'язків
(ребер)
741 236 77 402 652 223 534 301
Дата отримання даних Серпень 2007 9-11 грудня 2006
3 жовтня - 11
листопада 2006
Прикладне програмне забезпечення
82
У якості СКБД була використана MySQL,
що була розміщена на централізованому
сервері. Це зменшує продуктивність та
надійсність системи і є найслабшим та на-
більш навантаженним елементом системи.
У подальшому необхідно застосувати ідеї
розподіленого зберігання даних для змен-
шення навантаження на цю підсистему.
На самому початку level=1 для всих
зв’язків. По мірі опрацювання алгоритмом
даних додаються нові знайдені пари
пов’язаних людей і записується значення
level+1 у поле level.
Аналіз результатів експериментів
Експерименти здійснювались на
вищеописаному тестовому гріді та над ча-
стиною соціальних даних. Досліджувався
вплив розміру блоку даних що передається
на обробку обчислювачу, а також приско-
рення обчислень для різної кількості обчи-
слювачів. У табл. 5 наведено звідну табли-
цю результатів експериментів та графічно
показано на рис. 7. Абсолютні значення
часу виконання є доволі неточними, оскі-
льки на час здійснення тестових запусків
швидкість передачі даних між сервером
БД була порівняно малою.
При збільшенні розміру блоку да-
них, що формує одну підзадачу, зменшу-
ються додаткові витрати на координуван-
ня, але у разі помилки під час виконання
задачі та ж сама задача підлягає виконан-
ню з самого початку. Для уникнення поді-
бних ситуацій можна зберігати проміжні
результати підзадачі в разі неможливості її
завершення на поточному вузлі, наступна
буде продовжувати з останнього збере-
женного стану. В платформі GridGain це
технологія має назву GridCheckPointSPI.
Прискорення обчислень при вико-
ристанні 2 обчислювачів замість одного
склало приблизно 1.2, а при використанні
Таблиця 4. Формат зберігання даних
Поле Формат даних Опис
userID BIGINT, 8 знаків Ідентифікатор актора
friendID BIGINT, 8 знаків Ідентифікатор пов’язаного з ним актора
level TINYINT, 2 знаки Довжина соціального ланцюга, 1 – безпосередньо зна-
йомі
Таблиця 5. Результати експериментів, час у мс
Дані 1 вузол 2 вузли 4 вузли
50 по 10 24342 39180 50334
100 по 10 45647 46401 514431
150 по 10 111270 103450 80453
300 по 10 410849 410849 350478
500 по 50 1008168 816540 715521
300 по 100 410849 309557 250521
500 по 100 1008168 746542 675125
Прикладне програмне забезпечення
82
………………………………………………
……………………………………………….
чотирьох 1.6, при бажаних теоретичних
значеннях 2 та 4.
Значна деградація швидкості обчи-
слень зв’язана з наявністю централізованої
бази даних, яка й обмежує подальше маш-
табування. Як зазначалось раніше, для ви-
рішення цієї проблеми можна використати
розподіл навантаження прив’язанний до
даних. У якості системи кешування доці-
льно використати JBoss Cache, оскільки
він легко інтергрується з GridGain і його
складовою частиною є JGroups, який вико-
ристовується у тестовому гріді для «пошу-
ку» вузлів. Це дозволить зменшити пере-
силку даних між сервером БД та обчислю-
вальними вузлами.
Висновки
У даній роботі розглянуто питання
аналізу соціальних мереж, а саме операти-
вних мереж, та використання Грід-
технологій для вирішення задач зберігання
соціальних даних та їх аналізу. Зроблено
поверхневий огляд технологій, що засто-
совується для створення рішення.
Отримані результати експериментів
не відповідають очікуваним, що зв’язано з
невдало обраним методом доступу до да-
них.
Автор планує продовжити дослі-
дження в даному напрямі та використати
отримані результати для покращення хара-
ктеристик системи. Втілення у життя за-
пропонованих методів рішення поточних
обмежень
має……………………………………………
дозволити здійснити повноцінний аналіз
великих соціальних мереж. Також плану-
ється створити Web-інтерфейс для більш
зручної роботи з початковими соціальними
даними, результами аналізу та моніторин-
гу процесу обчислення задач Грідом.
1. http://www.gartner.com/it/page.jsp?id=739613
2. Fowler J. Legislative Cosponsorship
Networks in the U.S. House and Senate //
Social Networks. – 2005. – № 28(4). –
P. 454–465.
3. Ressler S. Social Network Analysis as an
Approach to Combat Terrorism: Past,
Present, and Future Research // Homeland
security affairs. – 2006. – P. 28–59.
4. Hanneman R. Introduction to Social Network
Methods, Department of Sociology teaches
the course at the University of California,
Riverside. – http://www.hsaj.org
5. Leskovec J., Horvitz E. Planetary-Scale
Views on a Large Instant-Messaging
Network // WWW 2008, April 21–25, 2008,
Beijing, Chine.
6. Dellamaggiore N., Smith E. LinkedIn – A
Professional Social Network Built with
Java™ Technologies and Agile Practices –
http://www.slideshare.net/linkedin/linkedins-
communication-architecture.
7. http://www.facebook.com/press/info.php?stat
istics
8. http://uk.wikipedia.org/wiki/ Соціаль-
на_мережа
9. http://www.insna.org/software/index.html
Рис. 7. Час обчислень у залежності від кількості вершин та обчислювачів
Прикладне програмне забезпечення
83
10. Huisman M., Duijn M. Software for Social
Network // Analysis Proceedings of the Sixth
International Conf. on Logic and
Methodology, August 17–20, 2004,
Amsterdam, The Netherlands.
11. http://pajek.imfm.si
12. Dean J., Ghemawat S. MapReduce:
Simplified Data Processing on Large Clusters
// Operating System Design and
Implementation (OSDI 2004), December 6-8,
2004, San Francisco, California, USA.
13. Russell C., Cole K. Grid Technologies for
Social Science: the SAMD Project //
IASSIST. – 2003. – № 4. – P. 5–9.
14. Дорошенко А.Е., Алистратов О.В., Тыр-
чак Ю.М. Системы Grid-вычислений – пе-
рспектива для научных исследований //
Проблемы программирования. – 2005. –
№ 1.– С. 14–38.
15. GridGain – http://gridgain.com
16. Lea D. A Java Fork/Join Framework // In
Proceedings of the ACM 2000 Java Grande
Conf. – 2000. – P. 36–43.
17. http://www.jgroups.org/
18. Mislove A., Marcon M., Gummadi K.P.,
Druschel P., Bhattacharjee S. Measurement
and Analysis of Online Social Networks //
IMC’07, October 24-26, 2007, San Diego,
California, USA.
Отримано 05.01.2009
Про автора:
Ткаченко Віра Василівна,
студентка 6-го курсу ФІОТ НТУ
України «КПІ»
Тел.: 8-(050) 346 0657
vera@tkachenko.kiev.ua
Веб-сторінка проекту: http://sna.org.ua
|
| id | pp_isofts_kiev_ua-article-1009 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-13T01:00:10Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/44/4ef1d6e05294aea5c5344ebfa470cd44.pdf |
| spelling | pp_isofts_kiev_ua-article-10092026-06-12T14:33:31Z Grid technologies for social network analysis Использование грид-технологий для анализа социальных сетей Використання Грід-технологій для аналізу соціальних мереж Tkachenko, V.V. UDC 681.3 УДК 681.3 УДК 681.3 This article deals with researching the ability of using Grid-technologies for solving problems of social networks analysis. One of the method of social analysis is implemented and experimental computations with the data from real online social networks were conducted. Determined pros and cons of chosen method of solving task and ways of overcoming them offered.Problems in programming 2009; 1: 73-84 Рассмотрен вопрос возможности и целе-сообразности использования Grid-технологий для решения задачи анализа социальных сетей. Реализован один из методов социаль-ного анализа и проведены экспериментальные вычисления на тестовой Grid системе с использованием социальных данных из реа-льных социальных сетей. Определены недо-статки выбраного метода решения задачи и приведены пути их преодоления.Problems in programming 2009; 1: 73-84 Розглянуто питання можливості та доцільності використання Grid-технологій для вирішення задачі аналізу соціальних мереж. Реалізовано один з методів соціального аналізу та проведено експериментальні обчислення на тестовій Grid системі з використанням соціальних даних з реальних соціальних мереж. Визначено недоліки обраного методу розв’язання задачі та окреслено шляхи їх подолання.Problems in programming 2009; 1: 73-84 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-06-12 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1009 PROBLEMS IN PROGRAMMING; No 1 (2009); 73-84 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2009); 73-84 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2009); 73-84 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1009/1077 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | UDC 681.3 Tkachenko, V.V. Grid technologies for social network analysis |
| title | Grid technologies for social network analysis |
| title_alt | Использование грид-технологий для анализа социальных сетей Використання Грід-технологій для аналізу соціальних мереж |
| title_full | Grid technologies for social network analysis |
| title_fullStr | Grid technologies for social network analysis |
| title_full_unstemmed | Grid technologies for social network analysis |
| title_short | Grid technologies for social network analysis |
| title_sort | grid technologies for social network analysis |
| topic | UDC 681.3 |
| topic_facet | UDC 681.3 УДК 681.3 УДК 681.3 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1009 |
| work_keys_str_mv | AT tkachenkovv gridtechnologiesforsocialnetworkanalysis AT tkachenkovv ispolʹzovaniegridtehnologijdlâanalizasocialʹnyhsetej AT tkachenkovv vikoristannâgrídtehnologíjdlâanalízusocíalʹnihmerež |