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

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

• Гомофілія [5] (англ. Homophily) — ступінь, в якій користувач утворює зв'язки з подібними. Подібність може бути визначене за ст́аттю, віком, соціальним станом, освітнім рівнем тощо[6].

• Множинність (англ. Multiplexity) — число «множинних» зв'язків, в яких знаходяться користувачі[7]. Наприклад, два користувача, які товаришують та працюють разом, будуть мати «множинність», рівну 2[8]. «Множинність» пов'язують з «силою зв'язку».

• Взаємність (англ. Mutuality/Reciprocity) — ступінь, в якій користувачі взаємодіють між собою, відповідають взаємністю на дії один одного[9].

• Мережева закритість (англ. Network Closure) — ступінь, в якій друзі користувача є друзями один одному. Також її називають «мірою повноти реляційних тріад». Припущення того, що користувач знаходиться в мережевій закритості, називається Транзитивність. [10]

• Сусідство (англ. Propinquity) — тенденція користувачів мати велику кількість зв'язків з географічно близькими користувачами[9].

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

• Міст (англ. Bridge) — користувач, чиї слабкі зв'язки заповнюють «структурні діри», що забезпечує єдиний зв'язок між іншими користувачами або кластерами (групами користувачів). Також через нього проходитиме найкоротший маршрут[11].

• Центральність — показник «важливості» або «впливу» певного користувача (кластера користувачів) всередині графа[12][13].

Стандартні методи вимірювання «центральності» включають в себе центральність за посередництвом[14], центральність за близькістю[14], центральність за впливовістю, альфа-центральність та центральність за степенем[14][15].

• Густина (англ. Density) — частка прямих зв'язків у мережі по відношенню до загального числа можливих[16][17].

• Відстань (англ. Distance) — мінімальну кількість зв'язків, необхідних для встановлення наявності взаємозв'язку між двома окремими користувачами.

• Структурні діри (англ. Structural holes) — відсутність зв'язків між двома частинами мережі.

• Сила зв'язку (англ. Tie Strength) визначається лінійною комбінацією часу, «близькості» та «взаємності»[11]. Чим більше значення сили зв'язку, тим вона сильніше. Сильні зв'язки визначає «гомофілія», «сусідство» або «транзитивність», в той час як слабкі зв'язки визначають «мости».

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

• Кліка (англ. Cliques) — група, в якій всі користувачі мають «прямі» зв'язки (вершини пов'язані (з'єднані) ребром) один до одного[18].

• Соціальне коло (англ. Social circles) — група, в якій не обов'язкові «прямі» зв'язки між користувачами[19].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. пошук в ширину
2. жадібні алгоритми

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

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

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

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

• По-перше, важко отримати соціальний граф від «провайдерів»[32] через цінність та захист законом соціальних даних.

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