№17 Теорія графів і соціальні мережі
Теорія графів знаходить застосування, наприклад, в геоінформаційних системах. Існуючі або знову проектовані будинки, споруди, квартали і т. П. Розглядаються як вершини, а що з`єднують їх дороги, інженерні мережі, лінії електропередачі і т. П. - як ребра.
Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об`їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.
Історія виникнення теорії графів
Родоначальником теорії графів вважається видатний математик, член Петербурзької академії наук Леонард Ейлер.
У 1736 році в одному зі своїх листів він формулює і пропонує рішення задачі про сім Кенігсбергськая мостах, що стала згодом однією з класичних задач теорії графів.
З давніх-давен серед жителів Кенігсберга була поширена така загадка: як пройти по всіх мостах (через річку Преголя), не проходячи за жодним з них двічі. Багато кёнігсбержци намагалися вирішити цю задачу як теоретично, так і практично, під час прогулянок. Втім, довести або спростувати можливість існування такого маршруту ніхто не міг.
У 1736 році завдання про семи мостах зацікавила Леонарда Ейлера, про що він написав у листі італійському математику і інженеру Маріон від 13 березня 1736 року. У цьому листі Ейлер пише про те, що він зміг знайти правило, користуючись яким, легко визначити, чи можна пройти по всіх мостах, не проходячи двічі по жодному з них. Відповідь була «не можна».
На спрощеною схемою частини міста (графі) мостам відповідають лінії (дуги графа), а частинам міста - точки з`єднання ліній (вершини графа). В ході міркувань Ейлер прийшов до наступних висновків:
- Число непарних вершин (вершин, до яких веде непарне число ребер) графа має бути парне. Не може існувати граф, який мав би непарне число непарних вершин.
- Якщо все вершини графа парні, то можна, не відриваючи олівця від паперу, накреслити граф, при цьому можна починати з будь-якої вершини графа і завершити його в тій же вершині.
- Граф з більш ніж двома непарними вершинами неможливо накреслити одним розчерком.
Граф Кенігсбергськая мостів мав чотири (синім) непарні вершини (тобто всі), отже, неможливо пройти по всіх мостах, не проходячи за жодним з них двічі.
Зображення графів на площині
При зображенні графів на малюнках найчастіше використовується наступна система позначень: вершини графа зображуються точками або, при конкретизації сенсу вершини, прямокутниками, овалами і ін. Де всередині фігури розкривається зміст вершини (графи блок-схем алгоритмів).
Якщо між вершинами існує ребро, то відповідні точки (фігури) з`єднуються відрізком або дугою. У разі орієнтованого графа дуги замінюють стрілками, або явно вказують спрямованість ребра.
Не слід плутати зображення графа з власне графом (абстрактної структурою), оскільки одному графу можна зіставити не одне графічне представлення.
Зображення покликане лише показати, які пари вершин з`єднані ребрами, а які - ні. Часто на практиці буває важко відповісти на питання, чи є два зображення моделями одного і того ж графа чи ні (іншими словами, ізоморфні відповідні зображенням графи). Залежно від завдання, одні зображення можуть давати більш наочну картину, ніж інші.
Відео: Теорія мереж: 3. Основи теорії графів
соціальний граф
Соціальний граф (англ. Social graph) - це граф, вузли якого представлені соціальними об`єктами, такими як призначені для користувача профілі з різними атрибутами (наприклад: ім`я, день народження, рідне місто і т. Д.), Спільноти, медіа-контент і т. д., а ребра - соціальними зв`язками між ними.
Неявний соціальний граф (англ. Implicit social graph) - це такий граф, який можна сформувати на основі взаємодій користувача зі своїми «друзями» і групами «друзів» в соціальній мережі. У цьому графі на відміну від звичайного соціального графа немає явного вказівки «друзів», тобто немає явних соціальних зв`язків.
За допомогою соціальних графів вирішують такі завдання, як: ідентифікація корстувачів соціальний пошук- генерація рекомендацій по вибору «друзів», медіа-контенту, новостей- виявлення «реальних» зв`язків або збір відкритої інформації для моделювання графа.
Обробка даних соціальних графів пов`язана з низкою проблем, як наприклад відмінності соціальних мереж, закритість соціальних даних.
завдання
ідентифікація користувачів
Виявлення профілів, що належать одній людині, в декількох соціальних мережах. Вирішення цього завдання дозволяє отримати більш повний соціальний граф, що може бути корисно в багатьох задачах, таких як:
соціальний пошук
Пошук соціальних об`єктів (користувачів, їх даних, їх записів і т. Д.), Заснований на аналізі набору зв`язків, в яких знаходяться шукані об`єкти.
генерація рекомендацій
Важливим завданням є пошук точних алгоритмів генерації рекомендацій і пропозицій користувачам, який так само використовується при створенні графа інтересів на основі соціального графа.
- Рекомендація друзів - користувачі рідко ділять свої контакти на соціальні групи, але, тим не менш, вони неявно ділять ці контакти на кластери, через їх взаємодії в рамках соціальної мережі.
- Рекомендації контенту - рекомендації медіа-контенту, спільнот, новин і т. П.
Існують традиційні підходи в області рекомендаційних систем:
Відео: Лекція 4: Теорія графів
- Коллаборативна фільтрація - полягає в формуванні списку рекомендованих об`єктів на основі думок користувачів, які поводяться схожим чином.
- Фільтрація вмісту - грунтується на характеристиках предмета і відомої про нього інформації.
- Соціальні підходи - відштовхуються від соціальних зв`язків користувачів.
Виявлення «справжніх» зв`язків
Застосування підходу «розвідки на основі відкритих джерел» для виявлення дійсних зв`язків між користувачами, тобто справжніх друзів, родичів і т. П.
Граф інтересів
Граф інтересів - це онлайн представництво інтересів конкретної людини, отримане на основі його активності в соціальних мережах.
Вершинами графа є захоплення особистості, також вершиною може бути профіль людини в соціальній мережі, ребра графа відображають взаємини між вершинами графа.
За допомогою графа інтересів можна зрозуміти, що людина хоче зробити, купити, куди хоче піти, з ким може зустрітися, за чиїми повідомленнями йому цікаво стежити або за кого він готовий проголосувати.
Зв`язку в графі інтересів
У графі інтересів можуть існувати різні типи зв`язків, які дозволяють користувачеві виходити за рамки звичайних соціальних мереж. Наприклад, людині потрібно знайти відповідь на потрібну йому тему, який не може дати жоден зі старих друзів і знайомих. В цьому випадку вибудовується ланцюжок з трьох типів зв`язків:
- людина-людина (користувачі в соціальній мережі можуть взаємодіяти безпосередньо)
- людина-інтерес (то з чим користувач взаємодіє з соціальної мережі)
- інтерес-інтерес (схожі інтереси можуть бути пов`язані між собою)
Граф інтересів також може бути представлений у вигляді зваженого графа, в цьому випадку вага ребра означає силу взаємозв`язку між вершинами.
При побудові такого графа спочатку вводиться припущення про те, що взаємозв`язки мають однакову силу, наприклад, інтерес до машин і до театру невідомий, і взаємозв`язок двох інтересів встановлюється у вигляді нескінченно великого числа. Потім, якщо буде виявлено, що люди, які цікавляться машинами, поводяться схожим чином з тими людьми, які захоплюються театром, то значення ваги ребра між вершинами, що позначають дані захоплення, буде зменшено.
Відносини між графом інтересів і соціальних графом
Граф інтересів і соціальний граф тісно взаємопов`язані, але це не одне і те ж.
Граф інтересів використовується для створення мережі інтересів людей. У той час як Facebook та інші соціальні мережі організовані навколо друзів людини, тобто навколо соціального графа, мережі захоплень створені навколо інтересів особистостей, їх графа інтересів.
Подібно до того як соціальний граф - це карта взаємозв`язків особистості з тими, хто «слід» за нею в мережі, граф інтересів - це так само взаємозв`язок з інтересами особистості в мережі.
Таким чином, захоплення людини, представлені у вигляді графа інтересів, забезпечують засоби для подальшої персоналізації веб-простору, заснованої на перетині графа інтересів з веб-контентом. Граф інтересів або мережу інтересів в деяких випадках можуть бути отримані з соціального графа або соціальної мережі і можуть підтримувати і оновлювати зв`язку між вершинами на основі даної соціальної мережі.
Граф інтересів повинен бути точним і виразним, він повинен брати до уваги явно оголошені інтереси, наприклад, «Like» на Facebook або «інтереси» в профілі на LinkedIn, а також неявні інтереси, виведені на основі активності користувача, наприклад, такі як клацання мишею , коментарі, теги до фото і чек-іни. Соціальні мережі часто є джерелом цієї інформації.
Використання графа інтересів
Існує кілька способів використання графа інтересів, як з точки зору споживача, так і з точки зору бізнесмена. У поєднанні з соціальним графом, граф інтересів може бути застосований для встановлення зв`язків між користувачами в соціальних мережах або в реальному світі. У таких мережах користувачі можуть вказувати і ділитися своїми захопленнями, але при цьому їм не обов`язково знати один одного.
Граф інтересів так само може бути застосований в маркетингу, в цілях аналізу аудиторії проекту і подальших продажів на основі цієї інформації, для аналізу тональності тексту і для таргетированной реклами, заснованої на інтересах.
Наприклад, такі компанії як Twitter за допомогою графа інтересів мають можливість робити рекламу більш спрямованої на конкретного користувача, грунтуючись на його захоплення.
Також граф інтересів може використовуватися при створенні продукції з урахуванням побажань споживача, він допомагає визначити які особливості і можливості слід надати в наступних версіях. Граф інтересів має безліч інших застосувань включаючи завдання виявлення вмісту та фільтрації для надання рекомендацій по фільмах, книгах, музиці і так далі.
