Предсказание ссылки - Link prediction

В теория сети, предсказание ссылки проблема предсказания существования связи между двумя объектами в сети. Примеры прогнозирования ссылок включают прогнозирование дружеских связей между пользователями в социальная сеть, прогнозируя ссылки на соавторство в сеть цитирования и прогнозирование взаимодействий между генами и белками в биологическая сеть. Прогнозирование ссылок также может иметь временной аспект, когда, учитывая моментальный снимок набора ссылок во времени ${ displaystyle t}$ , цель - спрогнозировать ссылки на время ${ displaystyle t + 1}$ .Прогнозирование ссылок широко применяется. В электронной коммерции прогнозирование ссылок часто является подзадачей для рекомендации товаров пользователям. При курировании баз данных цитирования его можно использовать для дедупликации записей. В биоинформатике его использовали для прогнозирования белок-белковые взаимодействия (PPI). Он также используется для идентификации скрытых групп террористов и преступников в приложениях, связанных с безопасностью.^[1]

Определение проблемы

Рассмотрим сеть ${ Displaystyle G = (V, E)}$ , куда ${ displaystyle V}$ представляет узлы сущностей в сети и ${ Displaystyle E substeq | V |}$ Икс ${ displaystyle | V |}$ представляет собой набор "истинных" ссылок между объектами в сети. Нам дан набор объектов ${ displaystyle V}$ и подмножество истинных ссылок, которые называются наблюдаемые ссылки.Цель прогнозирования ссылок - выявить ненаблюдаемые истинные ссылки. Во временной формулировке прогнозирования ссылок наблюдаемые ссылки соответствуют истинным ссылкам в определенный момент времени. ${ displaystyle t}$ , и цель состоит в том, чтобы вывести набор истинных ссылок во время ${ displaystyle t + 1}$ Обычно нам также дается подмножество ненаблюдаемых ссылок, называемых потенциальные ссылки ${ displaystyle E '}$ , и нам нужно определить истинные ссылки среди этих потенциальных ссылок.

В формулировке двоичной классификации задачи прогнозирования ссылок потенциальные ссылки классифицируются как истинные или ложные. Подходы к прогнозированию ссылок для этого параметра изучают классификатор ${ displaystyle M_ {b}}$ который отображает ссылки в ${ displaystyle E '}$ на положительные и отрицательные метки, т.е. ${ displaystyle M_ {b}: E ' to {0,1 }}$ . В формулировке оценки вероятности потенциальные связи связаны с вероятностями существования. Подходы к прогнозированию ссылок для этой настройки изучите модель ${ displaystyle M_ {p}}$ который отображает ссылки в ${ displaystyle E '}$ к вероятности, т.е. ${ displaystyle M_ {p}: E ' to [0,1]}$ .

Подходы с одной ссылкой изучают модель, которая классифицирует каждую ссылку независимо. Подходы к структурированному прогнозированию фиксируют корреляцию между потенциальными связями, формулируя задачу как задачу прогнозирования коллективных связей. Подходы к прогнозированию коллективных ссылок изучают модель, которая совместно определяет все истинные ссылки среди набора потенциальных ссылок.

Задачу прогнозирования ссылок также можно сформулировать как экземпляр задачи оценки пропущенных значений, где график представлен в виде матрицы смежности с пропущенными значениями. Задача состоит в том, чтобы заполнить матрицу путем определения пропущенных значений. Методы, основанные на факторизации матрицы, обычно используют эту формулировку.

История

Задача прогнозирования ссылок привлекла внимание нескольких исследовательских сообществ, начиная от статистика и сетевая наука к машинное обучение и сбор данных. В статистике модели генеративных случайных графов, такие как стохастические блочные модели предложить подход к созданию связей между узлами в случайный граф Для новичков в социальных сетях Либен-Новелл и Кляйнберг предложили модели прогнозирования ссылок, основанные на различных мерах близости графов.^[2]Сообщество машинного обучения и интеллектуального анализа данных предложило несколько статистических моделей для прогнозирования ссылок, например Popescul et al. предложила модель структурированной логистической регрессии, которая может использовать реляционные функции.^[3]Модели локальной условной вероятности, основанные на атрибутах и структурных особенностях, были предложены O’Madadhain et al. ^[4]Getoor предложил несколько моделей, основанных на ориентированных графических моделях для прогнозирования коллективных ссылок.^[5]Другие подходили на основе случайных блужданий.^[6] и матричная факторизация также были предложены ^[7]С появлением глубокого обучения было предложено несколько подходов, основанных на встраивании графов, для прогнозирования ссылок.^[8]Для получения дополнительной информации о прогнозировании ссылок см. Опрос Getoor et al. ^[9] и Ю. и др. al.^[10]

Подходы и методы

Было предложено несколько подходов к прогнозированию ссылок, включая неконтролируемые подходы, такие как меры сходства, вычисляемые по атрибутам объекта, случайная прогулка и матричная факторизация основанные подходы и контролируемые подходы, основанные на графические модели и глубокое обучение.Подходы к прогнозированию связей можно разделить на две широкие категории в зависимости от типа базовой сети: (1) подходы к прогнозированию каналов для однородных сетей (2) подходы к прогнозированию каналов для гетерогенных сетей На основе типа информации, используемой для прогнозирования связей, подходы можно разделить на подходы, основанные на топологии, подходы на основе содержимого и смешанные методы.^[11]

Методы на основе топологии

Методы, основанные на топологии, в целом предполагают, что узлы с аналогичной сетевой структурой с большей вероятностью образуют связь.

Общие соседи

Это распространенный подход к прогнозированию ссылок, который вычисляет количество общие соседи. У сущностей с большим количеством общих соседей больше шансов иметь ссылку. Он рассчитывается следующим образом:

{ Displaystyle CN (A, B) = {| A cap B |}}

Слабым местом этого подхода является то, что он не принимает во внимание относительное количество общих соседей.

Мера Жаккара

В Жаккар Мера решает проблему общих соседей, вычисляя относительное количество общих соседей:

{ Displaystyle J (A, B) = {{| A cap B |} над {| A чашка B |}}}

Мера Адамика – Адара

В Мера Адамика – Адара ^[12] представляет собой сумму журнала пересечения соседей двух узлов. Это фиксирует сходство с двумя переходами, что может дать лучшие результаты, чем простые методы с одним переходом. Он рассчитывается следующим образом:

{ displaystyle A (x, y) = sum _ {u in N (x) cap N (y)} { frac {1} { log | N (u) |}},}

куда ${ displaystyle N (u)}$ это набор узлов, прилегающих к ${ displaystyle u}$ .

Мера Каца

Методы на основе соседей могут быть эффективны, когда количество соседей велико, но это не так в разреженных графах. В этих ситуациях уместно использовать методы, учитывающие более длительные прогулки. Мера Каца ^[13] это одна из метрик, которая это фиксирует. Он вычисляется путем поиска в графе путей длины ${ displaystyle t}$ на графике и суммируя счетчики каждой длины пути, взвешенные по весам, заданным пользователем.

Позволять А быть матрица смежности рассматриваемой сети. Элементы ${ displaystyle (a_ {ij})}$ из А - переменные, которые принимают значение 1, если узел я подключен к узлу j и 0 в противном случае. Полномочия А указывают на наличие (или отсутствие) связей между двумя узлами через посредников. Например, в матрице ${ displaystyle A ^ {3}}$ , если элемент ${ displaystyle (a_ {2,12}) = 1}$ , это указывает на то, что узел 2 и узел 12 соединены некоторой прогулкой длиной 3. Если ${ Displaystyle С _ { mathrm {Кац}} (я)}$ обозначает центральность Каца узлая, затем математически:

{ displaystyle C _ { mathrm {Katz}} (i) = sum _ {k = 1} ^ { infty} sum _ {j = 1} ^ {n} alpha ^ {k} (A ^ { k}) _ {ji}}

Обратите внимание, что в приведенном выше определении используется тот факт, что элемент в местоположении ${ displaystyle (я, j)}$ из ${ displaystyle A ^ {k}}$ отражает общее количество ${ displaystyle k}$ градусные связи между узлами ${ displaystyle i}$ и ${ displaystyle j}$ .

Методы на основе атрибутов узла

Узловое подобие Методы предсказывают наличие ссылки на основе сходства атрибутов узла.

Евклидово расстояние

Значения атрибутов представлены как нормализованный вектор и расстояние между векторами, используемыми для измерения сходства. Небольшие расстояния указывают на большее сходство.

Косинусное сходство

После нормализации значений атрибутов вычисление косинуса между двумя векторами является хорошей мерой сходства, при этом низкие значения указывают на большее сходство.

Смешанные методы

Смешанные методы объединяют методы на основе атрибутов и топологии.

Вложения графов

Вложения графов также предлагают удобный способ прогнозирования ссылок.^[8] Алгоритмы встраивания графов, такие как Node2vec, изучите пространство встраивания, в котором соседние узлы представлены векторами, чтобы в пространстве встраивания сохранялись такие меры сходства векторов, как сходство скалярных произведений или евклидово расстояние. Эти сходства являются функциями как топологических особенностей, так и сходства на основе атрибутов. Затем можно использовать другие методы машинного обучения для предсказания ребер на основе подобия векторов.

Вероятностные модели отношений

Вероятностная реляционная модель (PRM) определяет шаблон для распределения вероятностей по базам данных. Шаблон описывает реляционную схему для домена и вероятностные зависимости между атрибутами в домене. PRM вместе с конкретной базой данных объектов и ненаблюдаемых ссылок определяет распределение вероятностей по ненаблюдаемым ссылкам. ^[5]

Вероятностная мягкая логика (PSL)

Вероятностная мягкая логика (PSL) - это вероятностная графическая модель марковского случайного поля с потерями в шарнирах (HL-MRF). HL-MRF создаются с помощью набора шаблонных логических правил первого порядка, которые затем основываются на данных. PSL может сочетать атрибутивную или локальную информацию с топологической или реляционной информацией. Хотя PSL может включать в себя локальные предикторы, такие как косинусное подобие, он также поддерживает реляционные правила, такие как завершение треугольника в сети.^[14]

Марковские логические сети (MLN)

Марковские логические сети (MLN) - это вероятностная графическая модель, определенная над сетями Маркова. Эти сети определяются шаблонными логическими правилами первого порядка, которые затем основываются на обучающих данных. MLN могут включать как локальные, так и реляционные правила с целью прогнозирования ссылок.^[15]

Приложения

Предсказание ссылки находит разнообразное применение, но любой домен, в котором объекты взаимодействуют структурным образом, может получить выгоду от прогнозирования связи.^[16] Распространенным применением прогнозирования ссылок является улучшение показателей сходства для совместная фильтрация подходы к рекомендации. Прогнозирование ссылок также часто используется в социальных сетях, чтобы предлагать пользователям друзей. Он также использовался для прогнозирования преступных сообществ.

В биологии предсказание связей использовалось для предсказания взаимодействий между белками в сетях белок-белковых взаимодействий.^[17] Прогнозирование ссылок также использовалось для определения взаимодействий между лекарствами и целями с помощью прогнозирования ссылок. ^[18] Другое применение - прогнозирование сотрудничества в сетях научного соавторства.

Разрешение сущности, также известная как дедупликация, обычно использует прогнозирование связи, чтобы предсказать, являются ли два объекта в сети ссылками на один и тот же физический объект. Некоторые авторы использовали контекстную информацию в сетевых структурированных доменах для улучшения разрешения сущностей.^[19]

Прогнозирование ссылок в контексте сетевых эффектов использовалось для анализа тенденций к распространению по сетям и может использоваться для улучшения маркетинговых стратегий, в частности вирусного маркетинга.^{[нужна цитата ]}

Программные пакеты

Бесплатное программное обеспечение с открытым исходным кодом

Проприетарное программное обеспечение с бесплатными версиями и версиями с открытым исходным кодом

Проприетарное программное обеспечение

Смотрите также

Рекомендации

^ Аль Хасан, Мохаммед; Заки, Мохаммед (2011). «Прогнозирование ссылок в социальных сетях» (PDF). Цитировать журнал требует | журнал = (помощь)
^ Либен-Новелл, Дэвид; Клейнберг, Джон (2007). «Проблема прогнозирования ссылок для социальных сетей». Журнал Американского общества информационных наук и технологий. 58 (7): 1019–1031. Дои:10.1002 / asi.20591.
^ Папескул, Александрин; Унгар, Лайл (2002). «Статистическое реляционное обучение для прогнозирования ссылок» (PDF). Семинар по изучению статистических моделей на основе реляционных данных.
^ О’Мададхайн, Джошуа; Хатчинс, Джон; Смит, Padhraic (2005). «Алгоритмы прогнозирования и ранжирования сетевых данных на основе событий» (PDF). Журнал Американского общества информационных наук и технологий.
^ ^а ^б Гетур, Лиза; Фридман, Нир; Коллер, Дафна; Таскар, Бенджамин (2002). «Изучение вероятностных моделей ссылочной структуры» (PDF). Цитировать журнал требует | журнал = (помощь)
^ Бэкстрем, Ларс; Лесковец, Юре (2011). «Случайные блуждания с учителем: прогнозирование и рекомендация ссылок в социальных сетях». Дои:10.1145/1935826.1935914. S2CID 7851677. Цитировать журнал требует | журнал = (помощь)
^ Менон, Адитья; Элкан, Чарльз (2011). «Прогнозирование связи с помощью матричной факторизации» (PDF). Машинное обучение и обнаружение знаний в базах данных. Конспект лекций по информатике. 6912. С. 437–452. Дои:10.1007/978-3-642-23783-6_28. ISBN 978-3-642-23782-9.
^ ^а ^б Сяо, Хан; др., др. (2015). «От одной точки к множеству: встраивание графов знаний для точного прогнозирования ссылок». SIGMOD. arXiv:1512.04792.
^ Гетур, Лиза; Диль, Кристофер (2005). «Link Mining: обзор». Дои:10.1145/1117454.1117456. S2CID 9131786. Цитировать журнал требует | журнал = (помощь)
^ Ю, Филипс; Хан, Цзявэй; Фалуцос, Христос (2010). «Link Mining: модели, алгоритмы и приложения». Цитировать журнал требует | журнал = (помощь)
^ Аггарвал, Чару (2015). Сбор данных. Springer. С. 665–670.
^ Адамич, Люда; Адар, Этян (2003). «Друзья и соседи в сети». Социальные сети. 25 (3): 211–230. Дои:10.1016 / S0378-8733 (03) 00009-1.
^ Кац, Л. (1953). «Новый индекс статуса на основе социометрического анализа». Психометрика. 18: 39–43. Дои:10.1007 / BF02289026. S2CID 121768822.
^ Бах, Стивен; Брошелер, Матиас; Хуанг, Берт; Гетур, Лиз (2017). "Марковские случайные поля с потерями на шарнирах и вероятностная мягкая логика". Журнал исследований в области машинного обучения. 18: 1–67. arXiv:1505.04406.
^ Dominogs, Педро; Ричардсон, Мэтью (2006). «Марковские логические сети» (PDF). Цитировать журнал требует | журнал = (помощь)
^ Мартинес, Виктор (2016). «Обзор прогнозирования ссылок в сложных сетях». Опросы ACM Computing. 49 (4): 1–33. Дои:10.1145/3012704. S2CID 14193467.
^ Ци, Яньцзюнь (2006). «Оценка различных биологических данных и методов компьютерной классификации для использования в прогнозировании взаимодействия белков». Белки: структура, функции и биоинформатика. 63 (3): 490–500. Дои:10.1002 / prot.20865. ЧВК 3250929. PMID 16450363.
^ Шридар, Дханья; Фахреи, Шобейр; Гетур, Лиз (2016). «Вероятностный подход для коллективного прогнозирования лекарственного взаимодействия на основе сходства» (PDF). Биоинформатика. 32 (20): 3175–3182. Дои:10.1093 / биоинформатика / btw342. PMID 27354693.
^ Бхаттачарья, Индраджит; Getoor, Лиз (2007). «Разрешение коллективной сущности в реляционных данных». ACM-транзакции по обнаружению знаний из данных (TKDD). 1: 5. Дои:10.1145/1217299.1217304. HDL:1903/4241. S2CID 488972.

[hasan:snda11-1] Аль Хасан, Мохаммед; Заки, Мохаммед (2011). «Прогнозирование ссылок в социальных сетях» (PDF). Цитировать журнал требует | журнал = (помощь)

[nowell:jasist07-2] Либен-Новелл, Дэвид; Клейнберг, Джон (2007). «Проблема прогнозирования ссылок для социальных сетей». Журнал Американского общества информационных наук и технологий. 58 (7): 1019–1031. Дои:10.1002 / asi.20591.

[popescul:ijcaiws03-3] Папескул, Александрин; Унгар, Лайл (2002). «Статистическое реляционное обучение для прогнозирования ссылок» (PDF). Семинар по изучению статистических моделей на основе реляционных данных.

[madadhain:kddexp05-4] О’Мададхайн, Джошуа; Хатчинс, Джон; Смит, Padhraic (2005). «Алгоритмы прогнозирования и ранжирования сетевых данных на основе событий» (PDF). Журнал Американского общества информационных наук и технологий.

[getoor:jmlr02-5] а ^б Гетур, Лиза; Фридман, Нир; Коллер, Дафна; Таскар, Бенджамин (2002). «Изучение вероятностных моделей ссылочной структуры» (PDF). Цитировать журнал требует | журнал = (помощь)

[jure:wsdm11-6] Бэкстрем, Ларс; Лесковец, Юре (2011). «Случайные блуждания с учителем: прогнозирование и рекомендация ссылок в социальных сетях». Дои:10.1145/1935826.1935914. S2CID 7851677. Цитировать журнал требует | журнал = (помощь)

[menon:ecml11-7] Менон, Адитья; Элкан, Чарльз (2011). «Прогнозирование связи с помощью матричной факторизации» (PDF). Машинное обучение и обнаружение знаний в базах данных. Конспект лекций по информатике. 6912. С. 437–452. Дои:10.1007/978-3-642-23783-6_28. ISBN 978-3-642-23782-9.

[xiao:sigmod15-8] а ^б Сяо, Хан; др., др. (2015). «От одной точки к множеству: встраивание графов знаний для точного прогнозирования ссылок». SIGMOD. arXiv:1512.04792.

[getoor:sigkddexp05-9] Гетур, Лиза; Диль, Кристофер (2005). «Link Mining: обзор». Дои:10.1145/1117454.1117456. S2CID 9131786. Цитировать журнал требует | журнал = (помощь)

[yu:book10-10] Ю, Филипс; Хан, Цзявэй; Фалуцос, Христос (2010). «Link Mining: модели, алгоритмы и приложения». Цитировать журнал требует | журнал = (помощь)

[11] Аггарвал, Чару (2015). Сбор данных. Springer. С. 665–670.

[12] Адамич, Люда; Адар, Этян (2003). «Друзья и соседи в сети». Социальные сети. 25 (3): 211–230. Дои:10.1016 / S0378-8733 (03) 00009-1.

[13] Кац, Л. (1953). «Новый индекс статуса на основе социометрического анализа». Психометрика. 18: 39–43. Дои:10.1007 / BF02289026. S2CID 121768822.

[bach:jmlr17-14] Бах, Стивен; Брошелер, Матиас; Хуанг, Берт; Гетур, Лиз (2017). "Марковские случайные поля с потерями на шарнирах и вероятностная мягкая логика". Журнал исследований в области машинного обучения. 18: 1–67. arXiv:1505.04406.

[domingos:mlj06-15] Dominogs, Педро; Ричардсон, Мэтью (2006). «Марковские логические сети» (PDF). Цитировать журнал требует | журнал = (помощь)

[16] Мартинес, Виктор (2016). «Обзор прогнозирования ссылок в сложных сетях». Опросы ACM Computing. 49 (4): 1–33. Дои:10.1145/3012704. S2CID 14193467.

[17] Ци, Яньцзюнь (2006). «Оценка различных биологических данных и методов компьютерной классификации для использования в прогнозировании взаимодействия белков». Белки: структура, функции и биоинформатика. 63 (3): 490–500. Дои:10.1002 / prot.20865. ЧВК 3250929. PMID 16450363.

[18] Шридар, Дханья; Фахреи, Шобейр; Гетур, Лиз (2016). «Вероятностный подход для коллективного прогнозирования лекарственного взаимодействия на основе сходства» (PDF). Биоинформатика. 32 (20): 3175–3182. Дои:10.1093 / биоинформатика / btw342. PMID 27354693.

[19] Бхаттачарья, Индраджит; Getoor, Лиз (2007). «Разрешение коллективной сущности в реляционных данных». ACM-транзакции по обнаружению знаний из данных (TKDD). 1: 5. Дои:10.1145/1217299.1217304. HDL:1903/4241. S2CID 488972.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]