Аналіз складних мереж на прикладі соціальної мережі в Інтернет
Today Social Network Analysis (SNA) is rather actual research direction. A new branch of the discrete mathematics was developed. It is called complex network theory. Besides topology analysis, it explores characteristics of each node and of the entire network. This article covers the exploration o...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2009
|
| Назва видання: | Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/27776 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Аналіз складних мереж на прикладі соціальної мережі в Інтернет / Ю.О Головін, А.Ю. Головін // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 51. — С. 166-171. — Бібліогр.: 5 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-27776 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-277762011-12-17T00:02:06Z Аналіз складних мереж на прикладі соціальної мережі в Інтернет Головін, Ю.О. Головін, А.Ю. Today Social Network Analysis (SNA) is rather actual research direction. A new branch of the discrete mathematics was developed. It is called complex network theory. Besides topology analysis, it explores characteristics of each node and of the entire network. This article covers the exploration of one of the biggest social network in Internet. 2009 Article Аналіз складних мереж на прикладі соціальної мережі в Інтернет / Ю.О Головін, А.Ю. Головін // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 51. — С. 166-171. — Бібліогр.: 5 назв. — укр. XXXX-0067 http://dspace.nbuv.gov.ua/handle/123456789/27776 621.3 uk Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Today Social Network Analysis (SNA) is rather actual research direction. A new
branch of the discrete mathematics was developed. It is called complex network
theory. Besides topology analysis, it explores characteristics of each node and of the entire network. This article covers the exploration of one of the biggest social network in Internet. |
| format |
Article |
| author |
Головін, Ю.О. Головін, А.Ю. |
| spellingShingle |
Головін, Ю.О. Головін, А.Ю. Аналіз складних мереж на прикладі соціальної мережі в Інтернет Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
| author_facet |
Головін, Ю.О. Головін, А.Ю. |
| author_sort |
Головін, Ю.О. |
| title |
Аналіз складних мереж на прикладі соціальної мережі в Інтернет |
| title_short |
Аналіз складних мереж на прикладі соціальної мережі в Інтернет |
| title_full |
Аналіз складних мереж на прикладі соціальної мережі в Інтернет |
| title_fullStr |
Аналіз складних мереж на прикладі соціальної мережі в Інтернет |
| title_full_unstemmed |
Аналіз складних мереж на прикладі соціальної мережі в Інтернет |
| title_sort |
аналіз складних мереж на прикладі соціальної мережі в інтернет |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2009 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/27776 |
| citation_txt |
Аналіз складних мереж на прикладі соціальної мережі в Інтернет / Ю.О Головін, А.Ю. Головін // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 51. — С. 166-171. — Бібліогр.: 5 назв. — укр. |
| series |
Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
| work_keys_str_mv |
AT golovínûo analízskladnihmerežnaprikladísocíalʹnoímerežívínternet AT golovínaû analízskladnihmerežnaprikladísocíalʹnoímerežívínternet |
| first_indexed |
2025-07-02T22:20:52Z |
| last_indexed |
2025-07-02T22:20:52Z |
| _version_ |
1836575467680825344 |
| fulltext |
програмне забезпечення інтелектуальних систем" (МР7^-2008). -
Дніпропетровськ : В-во ДНУ, 2008. - С. 266-267.
3. Мейер Д. Теория реляционных баз данных: Пер. с англ. / Д. Мейер. - М.: Мир,
1987. - С.9-19.
УДК 621.3
Ю.О.Головін, к.т.н., доцент, А.Ю. Головін, ІСЗЗІ НТУУ «КПІ», м. Київ
АНАЛІЗ СКЛАДНИХ МЕРЕЖ НА ПРИКЛАДІ СОЦІАЛЬНОЇ МЕРЕЖІ
В ІНТЕРНЕТ
Today Social Network Analysis (SNA) is rather actual research direction. A new
branch of the discrete mathematics was developed. It is called complex network
theory. Besides topology analysis, it explores characteristics of each node and of the
entire network. This article covers the exploration of one of the biggest social network
in Internet.
Аналіз соціальних мереж зараз широко використовується в економіці
(аналіз ринків), менеджменті (відносини між підприємствами та в середині
організацій), соціології, медицині (розповсюдження вірусів інфекцій) та
криміналістиці (взаємозв'язки терористичних організацій, шляхи
розповсюдження наркотиків та зброї).
У соціальних мережах є концепція «малого світу». Згідно неї, обравши
будь-яку людину поміж всього населення Землі, з'ясовується що вона,
фактично, може спілкуватися з будь-якою іншою людиною на Землі,
166 © Ю.О.Головін, А.Ю. Головін
Поступила 19.01.2009р.
Вступ.
Рис.1. Структурна схема зв'язків
використовуючи тільки свої власні знайомства. За результатами досліджень,
проведених у 1950-х та 1970-х роках виявилось, що ці дві людини (A та B на
Рис.1) зв'язані між собою в середньому через 5 посередників (6 зв'язків), а в
середині однієї країни ця відстань може становити 3 посередники. Так
виникло поняття «відношення через шістьох» (Six degrees of separation).
В даній статті представлений власний механізм аналізу соціальних
мереж, виконана її візуалізація, а також підтверджено, що концепція «малого
світу» справедлива для реальної соціальної мережі в Інтернет.
Основна частина.
Для побудови моделі мережі використовувався Інтернет-робот,
реалізований на мові Perl. Робот сканує анкети в соціальній мережі (що
налічує більш ніж 30 мільйонів користувачів) та збирає інформацію про
відносини між користувачами, тобто будує залежності персона-її друзі. Було
зроблено декілька вибірок для порівняння характеристик мережі в залежності
від її масштабу.
Треба зазначити, що дослідженню підлягала лише деяка частина мережі.
Це обумовлено складністю застосування алгоритмів для підрахунку
характеристик мережі (зокрема - алгоритму по знаходженню мінімального
шляху між вузлами), а також тим, що соціальна мережа являє собою
динамічну структуру, яка постійно еволюціонує. В процесі дослідження було
виявлено, що мережа зберігає свої властивості при зміні масштабу вибірки.
Це означає, що результати проведеного дослідження можна поширити на всю
соціальну мережу.
З математичної точки зору соціальну мережу можливо представити
графом, вершинами якого є люди, а ребрами - зв' язки між ними.
Для аналізу соціальних мереж використовується цілий ряд кількісних і
якісних характеристик, таких як ступінь централізації, ступінь
кластерності, зв 'язність, середня відстань.
Розглянемо властивості складних мереж, що були досліджені в даній
роботі:
1. Відстань між вузлами мережі. Застосовуючи це поняття до соціаль-
ної мережі визначимо, що відстань - це шлях (кількість проміжних персон)
між двома довільними людьми (акторами). Для визначення найкоротшого
шляху між всіма парами людей (вершин графа) використовувався алгоритм
Флойда-Уоршола. За допомогою цього алгоритму можна знайти найкоротші
шляхи між всіма парами вершин. Вхідними даними алгоритму є матриця
суміжності Gj, елементами якої є «1» (якщо існує ребро між вершинами i та
j), а також деяке велике число «о>» (якщо зв'язку немає). На виходи
отримуємо матрицю Dj, в кожному елементі якої буде довжина
найкоротшого шляху між вершинами i та j.
2. Коефіцієнт кластерності. Для окремого вузла мережі він
167
визначається як відношення реальної кількості ребер, об'єднуючих між
собою найближчих сусідів, до максимально можливої 1 к (к-1)
2
clust =
кількість _ ребер
2 к (к-1)
де к - кількість вершин.
3. Ступінь вузла. Даний параметр характеризує кількість прямих
сусідів даного вузла.
Також нас цікавлять значення максимальної та мінімальної відстані для
кожного вузла та для мережі в цілому.
Обрахунок характеристик здійснювався для вибірок в 418, 546, 642, 929,
1196, 1754, 2334 та 3500 користувачів.
Фрагмент результатів обрахунку зображено на Рис.2:
V e r t e x 8 5 8 :
. d e g r e e = 1 1
. c e n t r i c i t y = 0 . 0 1014
. a v e r a g e p a t h = 2 . 8 7 5 0 0
.max p a t h = 3
V e r t e x 8 6 9 :
. d e g r e e = 3 5
. c e n t r i c i t y = 0. 03226
. a v e r a g e p a t h = 2 . 8 2 6 5 1
.max p a t h = 3
V e r t e x 8 7 0 :
. d e g r e e = 1
. c e n t r i c i t y = 0 . 0 0 0 9 2
. a v e r a g e p a t h = 3 . 7 4 0 3 0
.max p a t h = 4
w h o l e n e t w o r k :
. c l u s t e r i ng = 0 . 0 02 52
. a v e r a g e p a t h = 3 . 6 1 2 8 4
. v e r t e x e s : 9 2 9
. e d j e s : 1 0 8 5
.max p a t h = 4
Рис.2. Результати обчислень
З результатів видно, що для вибірки в 929 персон середня величина
найкоротшого шляху становить 3,61284, а максимальна - не перевищує 4.
Тобто будь-яка людина в досліджуваній вибірці може зв'язатися з довільною
людиною максимум через 4 посередника. Динаміка величини середнього
шляху для різних масштабів вибірок зображена на Рис.3.:
Для невеликих вибірок значення найкоротшого середнього шляху
сильно варіюється, але для більш-менш великої кількості персон - виходить
на стійку величину, близьку до 5. Безперечно, із збільшенням масштабів
вибірки ця величина буде дещо зростати, але, навіть, для досить великої
кількості персон (десятки мільйонів) - не перевищить 8-9 посередників.
168
Рис.4. Візуалізація мережі програмою aiSee
169
Візуалізація мережі виконувалась за допомогою програм аіБее (Рис.4) та
ТвискОгарк (Рис.5).
aiS.ee автоматично малює план графів, що описуються на мові вБЬ .
Засобами аі8ее була виконана візуалізація мережі із 10000 користувачів
соціальної мережі. В центрі видно велике скупчення акторів навколо
«лідера» - людини, у якої найбільше прямих зв'язків. Найчастіше це
політичний діяч, зірка або просто дуже популярна персона.
Також в мережі присутні «посередники» - актори, що поєднують різні
підгрупи. Посередники мають авторитет перед іншими учасниками
соціальної мережі, адже вони є важливою ланкою, учасниками багатьох груп,
та, по суті, кістяком мережі.
Третій тип акторів - «замикаючі». Замикаючі знаходяться на окраїнах
мережі. Найчастіше такі люди не можуть або не бажають заводити прямі
контакти із іншими. Такі актори не є корисними для мережі, а лише
додатково навантажують її. Цілком можливо, що ці людини - новачки у
мережі і тільки намагається ввійти в колектив. В інакшому випадку треба
видаляти таких користувачів із мережі або проводити комплекс мір щодо
збільшення прямих зв'язків із іншими користувачами.
TouchGraph схожий по функціональному призначенню продукт.
Основною відмінністю є те, що вхідні дані не потребують особливого опису і
можуть бути імпортовані, наприклад, з Excel. Додатковою є функція
виділення підгруп (кластерів, клік), а також можливість фільтрації.
170
Наприклад, можливо відфільтрувати замикаючих (із незначною кількістю
зв'язків).
Ще однією можливістю відображення мережі є її представлення у
вигляді кругової діаграми (Рис.6). Це зроблено із застосуванням графічної
бібліотеки GD мови Perl.
Рис.6. Візуалізація мережі у вигляді кругової діаграми
Кругова діаграма дозволяє оцінити ступінь вузла. Вузли із найбільшою
кількість зв'язків знаходяться зверху.
Висновки
В результаті виконаних досліджень було розроблено власний метод
аналізу складних мереж на прикладі соціальної мережі в Інтернет та
виконано декілька варіантів візуалізації мережі.
Щодо результатів аналізу, то ми переконалися у вірності теорії «малого
світу». Дійсно, зв'язки між опосередкованими людьми є не такими далекими,
як це здається на перший погляд.
Соціальна мережа, по суті, являє собою об'єднання тисяч підмереж. Чим
швидше розвиваються ці підмережі, тим швидший розвиток мережі в цілому.
1. Ландэ Д.В., Снарский А.А. Динамическая сеть понятий из веб-публикаций
http://www.infostream.com.ua/infostream/news48/dinam-dwl.pdf
2. ДавыдовА.А. Системная социология, изд.ЛКИ 2007 - 248 с.
3. Сазанов В.М. Социальные сети http://ntl-cbm.narod.ru/CBM-NET/cbm-net.ppt
4. Прохоров А., Ларичев Н. Компьютерная визуализация социальных сетей
www.compress.ru/article.aspx?id=16593&iid=771
5. Матеріали сайту http:// wikipedia.org/
Поступила 16.02.2009р.
171
http://www.infostream.com.ua/infostream/news48/dinam-dwl.pdf
http://ntl-cbm.narod.ru/CBM-NET/cbm-net.ppt
http://www.compress.ru/article.aspx?id=16593&iid=771
УДК 004.942
Тарік (Мох'д Тайсір) Алі Аль Омарі, аспірант НУ «Львівська політехніка»,
В.М.Теслюк, к.т.н., доцент кафедри САП, НУ «Львівська політехніка»,
П.Ю.Денисюк, к.т.н., ст. викл. кафедри САП, НУ «Львівська політехніка»,
Хамза Алі Юсеф Аль Шавабкех, аспірант НУ «Львівська політехніка».
РОЗРОБЛЕННЯ МОДЕЛІ ДЛЯ ОПТИМІЗАЦІЇ КОНСТРУКТИВНИХ
ПАРАМЕТРІВ АКУСТИЧНИХ ЕЛЕМЕНТІВ МЕМС
У статті представлено розроблене інформаційне, лінгвістичне та
математичне забезпечення підсистеми для розв'язання задач
багатокритеріальної оптимізації. Побудована модель для оптимізації
конструкційних параметрів акустичних елементів МЕМС та наведено
результати.
In the article the information, linguistic and mathematical software of subsystem
for the decision of tasks of multicriterion optimization are developed. The model for
optimization of construction parameters of acoustic elements of MEMS is built and
results are presented.
Вступ
При розроблені об'єктів різного функціонального призначення виникає
потреба в розв'язанні 3 типів задач: аналізу, синтезу та оптимізації [1]. Ядром
задач синтезу є оптимізація, яка призначена для знаходження найкращих
результатів для об'єкта проектування в заданих умовах. У задачах
оптимізації з одним критерієм потрібно визначити відповідне значення
цільової функція. Під час аналізу та синтезу складних об'єктів та систем
виникає проблема з необхідністю досягнення декількох цілей, які частково
або повністю суперечать одна одній. Один з шляхів розв'язання задач
багатокритеріальної оптимізації (ЗБО) пов'язаний з вибором одного
домінуючого, а інші приймаються як обмеження і оптимізація проводиться
по домінуючому критерію. Такий підхід до розв' язання практичних задач
значно знижує їх ефективність. Відомі системи для розв' язання задач
лінійного програмування та імітаційного моделювання MATHCAD,
MATLAB не дають можливості переглянути хід розв'язку та проміжні данні
розрахунку. Тому, робота, яка присвячена розробленню підсистеми для
розв' язання задач багатокритеріальної оптимізації є актуальною.
1. Формулювання багатокритеріальної оптимізаційної задачі
Задача багатокритеріального математичного програмування має такий
вигляд, знайти оптимум для цільових функцій [2-6] :
© Тарік (Мох'д Тайсір) Алі Аль Омарі, В.М.Теслюк,
172 П.Ю.Денисюк, Хамза Алі Юсеф Аль Шавабкех
|