Соціальний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
На даній анімації показані в яких стосунках перебувають різні соціальні об'єкти. Користувач Єва знаходиться в дружніх відносинах з користувачами Адам і Кейт, при цьомуАдам і Кейт не є друзями один одному, але у них є спільний друг Єва. Фотографія Пітера була оцінена багатьма користувачами, в тому числі вона сподобалася і Єві. Також Єва слухає радіо з Last.fm і дивиться відео з Youtube.


Соціальний граф (англ. Social graph) — це граф, вузли якого представлені соціальними об'єктами, такими як профілі користувача з різними атрибутами (наприклад: ім'я, день народження, рідне місто, тощо), співтовариства, медіа-контент[1], тощо, а ребра — соціальними зв'язками між ними[2][3].

Неявний соціальний граф (англ. Implicit social graph) — це такий граф, який можна сформувати (вивести, обчислити) на основі взаємодій користувача зі своїми «друзями» та групами «друзів» в соціальній мережі. У цьому графі на відміну від звичайного соціального графа немає явної вказівки «друзів», тобто немає явних соціальних зв'язків[4].

Особливості соціального графа характеризується такими метриками, як: метрики взаємин, метрики зв'язків та сегментації. Для вирішення завдань на соціальному графі використовуються спеціальні моделі, за допомогою яких можна замінити «реальні» графи. За допомогою соціальних графів вирішують такі завдання, як: ідентифікація користувачів; соціальний пошук; генерація рекомендацій з вибору «друзів», медіа-контенту, новин, тощо; виявлення «реальних» зв'язків або збір відкритої інформації для моделювання графа. Обробка даних соціальних графів пов'язана з низкою проблем, як наприклад відмінності соціальних мереж, закритість соціальних даних.

Метрики[ред.ред. код]

Говорячи про завдання на соціальному графі, вживають термін метрики, які в числовій формі відображають характеристики соціальних об'єктів, сегментів/груп об'єктів та їх зв'язків. Ці метрики використовують при проведенні аналізу соціальних мереж.

Взаємовідносини[ред.ред. код]

Дані метрики відображають характер взаємовідносин одного соціального об'єкта з іншими соціальними об'єктами.

  • Гомофілія [5] (англ. Homophily) — ступінь, в якій користувач утворює зв'язки з подібними. Подібність може бути визначене за ст́аттю, віком, соціальним станом, освітнім рівнем, тощо. [6]
  • Множинність (англ. Multiplexity) — число «множинних» зв'язків, в яких знаходяться користувачі. [7] Наприклад, два користувача, які товаришують та працюють разом, будуть мати «множинність», рівну 2. [8] «Множинність» пов'язують з «силою зв'язку».
  • Взаємність (англ. Mutuality/Reciprocity) — ступінь, в якій користувачі взаємодіють між собою, відповідають взаємністю на дії один одного. [9]
  • Мережева закритість (англ. Network Closure) — ступінь, в якій друзі користувача є друзями один одному. Також її називають «мірою повноти реляційних тріад». Припущення того, що користувач знаходиться в мережевій закритості, називається Транзитивність. [10]
  • Сусідство (англ. Propinquity) — тенденція користувачів мати велику кількість зв'язків з географічно близькими користувачами. [9]

Зв'язки[ред.ред. код]

Дані метрики відображають особливості зв'язків, як для окремих соціальних об'єктів, так і для графа в цілому.

  • Міст (англ. Bridge) — користувач, чиї слабкі зв'язки заповнюють «структурні діри», що забезпечує єдиний зв'язок між іншими користувачами або кластерами (групами користувачів). Також через нього проходитиме найкоротший маршрут. [11]
  • Центральність (англ. Centrality) — ступінь, яка показує «важливість» або «вплив» певного користувача (кластера користувачів) всередині графа. [12][13]
Стандартні методи вимірювання «центральності» включають в себе центральність з посередництва, центральність по близькості, центральність власного вектора, альфа центральність та центральність за ступенем. [14]
  • Густина (англ. Density) — частка прямих зв'язків у мережі по відношенню до загального числа можливих. [15][16]
  • Відстань (англ. Distance) — мінімальну кількість зв'язків, необхідних для встановлення наявності взаємозв'язку між двома окремими користувачами.
  • Структурні діри (англ. Structural holes) — відсутність зв'язків між двома частинами мережі.
  • Сила зв'язку (англ. Tie Strength) визначається лінійною комбінацією часу, «близькості» та «взаємності».[11] Чим більше значення сили зв'язку, тим вона сильніше. Сильні зв'язки визначає «гомофілія», «сусідство» або «транзитивність», в той час як слабкі зв'язки визначають «мости».

Сегментація[ред.ред. код]

Дані метрики відображають характеристики соціального графа, поділеного на сегменти, які мають відмінні риси.

  • Кліка (англ. Cliques) — група, в якій всі користувачі мають «прямі» зв'язки (вершини пов'язані (з'єднані) ребром) один до одного. [17]
  • Соціальне коло (англ. Social circles) — група, в якій не обов'язкові «прямі» зв'язки між користувачами. [18]
  • Коефіцієнт кластеризації (англ. Clustering coefficient) — ступінь ймовірності того, що два різних користувача, пов'язані з конкретним індивідуумом. Високий коефіцієнт кластеризації вказує на високу замкнутість групи, іншими словами, група може бути «клікою».
  • Згуртованість (англ. Cohesion) — ступінь, в якій користувачі пов'язані між собою одним, загально-з'єднаним зв'язком, утворюючи соціальну згуртованість. Структурна згуртованість — вказує на таку єдину структуру групи, що видалення невеликої кількості користувачів веде до розриву групи. [17]


Моделі[ред.ред. код]

Модель соціальних графів

У цьому розділі наведені загальновідомі моделі графів, які потенційно можуть замінити «реальні» соціальний графи.[19]

Функціонально-керовані моделі (англ. Feature-driven Models) націлені на відтворення статистичних характеристик графа, таких як ступовий розподіл та динамічні зміни щільності графа.

Навмисно-керовані моделі (англ. Intent-driven Models) сфокусовані на емуляцію процесу створення оригінального графа.

  • Випадковий обхід/випадкові блукання (Random Walk)
  • Найближчий сусід (Nearest Neighbor)

Структурно-керовані моделі (англ. Structure-driven Models) охоплюють статистичні дані зі структури графа, дозволяючи відповідному генератору відтворювати випадкові графи з тими ж структурними обмеженнями.

  • Графи Кронекера (Kronecker graphs)
  • dK-графи (dK-graphs)

Завдання[ред.ред. код]

Ідентифікація користувачів[ред.ред. код]

Виявлення профілів, що належать одній людині, в декількох соціальних мережах. [20] Вирішення цієї задачі дозволяє отримати більш повний соціальний граф, що може бути корисно в багатьох задачах, таких як:

  1. Соціальний пошук
  2. Генерація рекомендацій[ru]

Соціальний пошук[ред.ред. код]

Пошук соціальних об'єктів (користувачів, їх даних, їх записів, тощо.), заснований на аналізі набору зв'язків, в яких знаходяться об'єкти котрі треба знайти.[3]

Генерація рекомендацій[ред.ред. код]

Важливим завданням є пошук точних алгоритмів генерації рекомендацій та пропозицій користувачам, які так само використовуються при створенні графа інтересів[ru] на основі соціального графа.

  • Рекомендація друзів — користувачі рідко ділять свої контакти на соціальні групи, але, тим не менш, вони неявно ділять ці контакти на кластери, через їх взаємодії в рамках соціальної мережі.[21]
  • Рекомендації контенту — рекомендації медіа-контенту, спільнот, новин, тощо.[22]

Підхід до рекомендацій

Існує традиційний підхід в області рекомендаційних систем[22]:

  • Коллаборативна фільтрація[ru][23] — полягає у формуванні списку рекомендованих об'єктів на основі думок користувачів, провідних себе схожим чином.
  • Фільтрація вмісту — ґрунтується на характеристиках предмета та відомої про нього інформації.
  • Соціальний підхід — відштовхуються від соціальних зв'язків користувачів.

Виявлення «справжніх» зв'язків[ред.ред. код]

Застосування підходу «розвідки на основі відкритих джерел[en]» (англ. Open source intelligence, OSINT) для виявлення істинних зв'язків між користувачами, тобто справжніх друзів, родичів, тощо.[24]

Збір інформації[ред.ред. код]

Побудова соціального графа на основі даних, отриманих внаслідок парсинга веб-сервісів провайдерів соціальних мереж.

Для оцінювання завдання відносяться такі критерії: [25]

  • Ефективність: наскільки швидко виявляють вузли/зв'язку внаслідок сканування,
  • Чутливість: як різні соціальні мережі та кількість захищених/закритих користувачів («чорної діри») впливають на обхід,
  • Відхилення: наскільки сильно відрізняються статистичні властивості підграфів, отриманих при обході, від властивостей вихідного графа.

При обході оцінюють такі фактори:

  • Вибір вузлів: вузли є відправною точкою обходу. Важливо вибрати правильні вузли та порядок обходу черг, щоб уникнути низької якості сторінки,
  • Алгоритми вибору вузлів: алгоритми вирішують, який вузол вибрати наступним. Часто використовувані алгоритми:
  1. пошук в ширину
  2. жадібні алгоритми
  • Захищені користувачі: через закритість соціальних даних, можна пропустити велику частину соціального графа. Різні алгоритми обходів впливають на таких користувачів по-різному,
  • Різні соціальні мережі: вони мають свої унікальні властивості, навіть якщо вони надають аналогічні послуги.

Проблеми[ред.ред. код]

Відмінності соціальних мереж[ред.ред. код]

Для задачі ідентифікації користувачів головною проблемою є відмінності соціальних мереж. Переважно грають роль семантика зв'язків між соціальними об'єктами та соціальні графи різних топологій. [20]

Генерація рекомендацій[ред.ред. код]

Основною проблемою генерації рекомендацій є проблема холодного старту — розрахунок рекомендації для нових соціальних об'єктів (користувачів, постів, медіа-контенту, тощо). [22]

Закритість соціальних даних[ред.ред. код]

Головна проблема збору даних для соціального графа полягає в закритості соціальних мереж. [26]

  • По-перше, важко отримати соціальний граф від «провайдерів»[27] через цінність та захист законом соціальних даних.
  • По-друге, великою проблемою є збір мільйонів списків контактів, профілів, фотографій, відео, тощо парсер. Багато «провайдери» соціальних мереж використовують Single Page Application або безліч динамічних сторінок, що містять Ajax та DHTML, що створює дуже багато проблем для створення гнучкого парсера.


Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Слово «медиа-контент» в словаре Академик
  2. Завдання ідентифікації користувачів в соціальних мережах, 2012, pp. 3
  3. а б Соціальний пошук, 2010, pp. 199
  4. Suggesting Friends, 2010, pp. 2
  5. Поняття гомофілія, 2012, pp. 168-169
  6. гомофілія, 2001, pp. 415-444
  7. Множинність, 1997, pp. 673-693
  8. Приклад множинності, 2003
  9. а б Розуміння соціальних графів, 2012
  10. Транзитивність, 2010, pp. 855-869
  11. а б Сила зв'язків, 1973, pp. 1360-1380
  12. Центральність, 2010, p. 32
  13. Метрики для базового мережевого аналізу, 2011, pp. 364-367
  14. Центральність вершин, 2010, pp. 245
  15. Аналіз соціальних мереж, 2006, pp. B-11 — B-12
  16. Соціальні мережі: техніки та додатки, 2010, pp. 25
  17. а б Кліка в аналізі соціальних мереж, 2011, pp. 149
  18. Метрики для базового мережевого аналізу, 2011, pp. 346-347
  19. Social Graph Models, 2010, pp. 3-4
  20. а б завдання ідентифікації користувачів в соціальних мережах, 2012, pp. 2-4
  21. Suggesting Friends, 2010, pp. 2-7
  22. а б в Рекомендації треків у соціальних мережах, 2012, p. 34
  23. Рекомендаційні системи на основі коллаборативной фільтрації, 2002, С. 187
  24. OSINT, 2012, pp. 21-39
  25. Crawling OSN, 2010, pp. 1-7
  26. Crawling OSN, 2010, pp. 1
  27. Crawling OSN, 2010, pp. 3

Література[ред.ред. код]

  • Н. В. Богатир Вкоріненість і за її межами: вплив мереж Міжнародна конференція «Вкоріненість і за її межами: пояснюють чи соціологічні теорії економічну реальність ?»Жовтень 25-28, 2012, Москва, Росія (2012) С. 168-169.