распространения влияния соц сетей это грех

Перейти к основному содержанию Рекламное объявление SpringerOpen Поиск Опубликовать Исследуйте журналы Книги О Авторизоваться Вычислительные социальные сети О Статьи Коллекции статей Правила подачи документов Исследовать Открытый доступ Опубликовано: 15 октября 2014 г. Разделение сообщества на основе влияния для социальных сетей Зайсинь Лу ,Юйцин Чжу ,Вэй Ли ,Вейли Ву иСючжэнь Чэн Вычислительные социальные сети объем 1 , Номер статьи: 1 ( 2014 ) Цитируйте эту статью 3723 доступа 23 цитаты Метрики Детали Абстрактный Предпосылки / Цель Разделение сообщества имеет большое значение в социологии, биологии и информатике. Из-за экспоненциально увеличивающегося количества приложений социальных сетей необходим быстрый и точный метод для разделения сообщества в социальных сетях. В связи с этим мы исследуем проблему разделения социальных сообществ с точки зрения распространения влияния, которое является одной из важнейших характеристик социальной коммуникации. Методы Мы формулируем разделение социальных сообществ как задачу комбинаторной оптимизации, которая направлена ​​на разделение социальной сети на K непересекающихся сообществ таким образом, чтобы сумма распространения влияния внутри каждого сообщества была максимальной. Когда K = 2, мы разрабатываем оптимальный алгоритм, который имеет доказуемую гарантию производительности для класса моделей распространения влияния. Для общего K мы доказываем, что -сложно найти максимальное разбиение для социальных сетей в хорошо известных линейных пороговых и независимых каскадных моделях. Чтобы получить решения, близкие к оптимальным, мы разрабатываем жадный алгоритм, основанный на оптимальном алгоритме. Мы также разрабатываем эвристический алгоритм с низкой вычислительной сложностью для крупных социальных сетей.NпNP Полученные результаты Чтобы оценить практическую эффективность наших алгоритмов, мы проводим имитационное исследование на основе реальных сценариев. Эксперименты проводятся в трех реальных социальных сетях, и результаты экспериментов показывают, что более точное разделение в соответствии с распространением влияния может быть получено с использованием наших алгоритмов, а не некоторых классических алгоритмов разделения сообщества. Выводы В этом исследовании мы исследуем проблему разделения сообщества в социальных сетях. Она сформулирована как задача оптимизации и исследована как теоретически, так и практически. Результаты могут быть применены для поиска сообществ в социальных сетях, а также полезны для проблемы распространения влияния в социальных сетях. 1. Фон 1.1 Мотивация Социальные сети - это междисциплинарная область исследований, которая в последние годы привлекла к себе большое внимание. Одной из важных проблем социальных сетей является разделение сообщества, которое обеспечивает понимание отношений и атрибутов пользователей, входящих в социальную сеть. Как правило, социальная сеть может быть смоделирована как граф, в котором узлы представляют пользователей, а края представляют отношения между пользователями. Цель раздела сообщества - сгруппировать пользователей в группы в соответствии с их топологией графов [ 1 ] - [ 8]. Еще одна важная проблема в социальных сетях - распространение влияния. Это одна из важнейших характеристик социальной коммуникации, которая играет важную роль в самых разных сферах, таких как распространение медицинских инноваций и популяризация новых технологий. Например, проблема максимизации влияния с целью найти небольшую группу пользователей в социальной сети в качестве семян для запуска большого распространения влияния имеет широкое применение в вирусном маркетинге [ 9 ] - [ 13 ]. Из-за недетерминированности человеческого поведения распространение влияния в основном изучается в вероятностных моделях, таких как модель линейного порога (LT) и модель независимого каскада (IC) [ 14 ] - [ 16 ], то есть поведение и решения пользователей. неуверенны и зависят от поведения других. Например, принятие пользователем нового продукта может повлиять на их друзей, принятие которых может в дальнейшем повлиять на других. Следовательно, вероятностные модели более подходят для моделирования распространения влияния в социальных сетях, чем детерминированные. К сожалению, одна важная проблема заключается в том, что ожидаемое распространение влияния по всей социальной сети трудно оценить для большинства вероятностных моделей, таких как LT и IC [ 15 ], [16 ]. Поэтому во многих работах (например, [ 15 ] - [ 17 ]) строится локальная область для каждого пользователя и используется локальное распространение влияния вместо глобального. Но в некоторых крупных социальных сетях могут быть миллионы пользователей, поэтому невозможно построить локальные области для всех пользователей. Есть также много работ, изучающих общинные алгоритмы для максимизации влияния, предполагая, что влияние редко распространяется в разных сообществах. Однако, по нашим наблюдениям, мало работ по разделению сообществ, специально направленных на распространение влияния в социальных сетях. Работоспособность алгоритмов, основанных на сообществе, не может быть гарантирована, если не существует точного разделения сообщества на основе влияния. В этой статье мы исследуем проблему, связанную с вопросом о том, как разделить социальную сеть на непересекающиеся сообщества с точки зрения распространения влияния. Мы считаем, что это исследование полезно для решения проблемы максимизации влияния и, возможно, активизирует дальнейшие исследования и потенциальные приложения сообщества в социальных сетях. 1.2 Сопутствующие работы Разделение сообщества имеет большое значение не только для социальных сетей, но и для таких областей, как компьютерные сети и биологические сети. Существует множество работ по разделению сообществ в общих сетях (например, [ 6 ], [ 8 ], [ 18 ], [ 19 ]), и много усилий было посвящено формализации интуиции, что сообщество - это набор узлов. наличие большего количества соединений друг с другом при меньшем количестве соединений с остальной частью сети. Первое исследование разделения сообществ было проведено Weiss et al. [ 20 ]. Для последующих подходов в основном есть четыре категории: методы на основе иерархии [ 1 ], [ 2 ], методы на основе спектра [ 3 ], [4 ], методы на основе плотности [ 5 ] и методы на основе модульности [ 6 ] - [ 8 ], [ 21 ] - [ 29 ]. В частности, понятие модульности Ньюмана [ 6 ], [ 8 ], которое рассматривает внутреннюю связность со ссылкой на рандомизированную модель, было очень популярной мерой для разделения сообщества в общих сетях. Несмотря на отличную производительность во многих реальных сетях, это семейство подходов обычно имеет проблемы с «пределом разрешения», т. Е. Методы на основе модульности отдают предпочтение более крупным сообществам и не могут обнаружить сообщества небольших размеров [ 25 ], [ 30].]. Поэтому в некоторых работах исследуются новые методы обнаружения сообществ, такие как методы саморегулирования и сравнительные методы [ 18 ]. Кроме того, в [ 19 ] Hu et al. предложил алгоритм с точки зрения узла, чтобы объединить узлы в сообщество с наибольшей силой притяжения. В [ 31 ] Zhang et al. предложил алгоритм с точки зрения комбинаторной оптимизации для разделения узлов на непересекающиеся части. Есть также много работ, в которых сообщества рассматриваются с разных точек зрения. Чтобы узнать больше о большом количестве работ по разделу сообщества, пожалуйста, обратитесь к [ 29 ], [ 32 ] - [ 37 ]. Помимо разделения сообщества, распространение влияния также является важным вопросом в социальных сетях. Домингос и Ричардсон в [ 13 ] и [ 12 ] впервые предложили общие описательные модели для распространения влияния в социальных сетях. В [ 14 ] Kempe et al. сформулировал распространение влияния как задачу оптимизации, а именно максимизацию влияния. Они доказали, что жадный алгоритм имеет доказуемую гарантию производительности для моделей LT и IC. Однако вопрос о том, как оценить ожидаемое распространение влияния для выбора узлов с максимальным предельным усилением, оставался открытой проблемой, и жадный алгоритм в [ 14] был реализован методом Монте-Карло (МК). После этого многие исследователи начали исследовать, как эффективно вычислить распространение влияния, и было предложено большое количество методов (например, [ 15 ], [ 16 ], [ 38 ]) для моделей LT и IC. Между тем, существует также множество работ, исследующих новые модели распространения влияния (например, [ 39 ], [ 40 ]) для приближения к реальным сценариям. Из-за природы сообществ применение исследования разделения сообществ для распространения влияния является многообещающим. В [ 17 ] Wang et al. предложил жадный алгоритм на основе сообщества для добычи наиболее влиятельных узлов. В [ 41 ] Ли и др. далее предложил алгоритм максимизации влияния в социальных сетях. Они предполагают, что распространение влияния каждого узла ограничено сообществом, в котором он находится, и поэтому они оценивают распространение влияния внутри каждого сообщества, чтобы повысить эффективность вычислений. Есть также много работ для распространения влияния или других приложений социальных сетей, использующих преимущества структур сообщества (см., Например, [ 42 ] - [ 45 ] для последних работ). 1.3 Наш вклад Несмотря на то, что по общему разделению сообщества проделано много работы, по нашим наблюдениям, мало работ сделано по разделению сообщества для распространения влияния. В связи с этим мы исследуем, как разделить социальную сеть на сообщества в соответствии с распространением влияния. Наши основные вклады заключаются в следующем: 1. Мы формально определяем основанную на влиянии проблему разделения сообщества как задачу комбинаторной оптимизации с целью разделения социальной сети на K непересекающихся сообществ так, чтобы сумма распространения влияния внутри каждого сообщества была максимальной. Мы называем проблему Максимальным K- разделением сообщества (M K CP). Мотивация состоит в том, чтобы сохранить как можно большее распространение влияния после разделения и уменьшить ошибки оценки, вызванные использованием локального распространения влияния, увеличенного по сравнению с глобальным. 2. Когда K = 2, т. Е. Разделение социальной сети на две непересекающиеся части, мы разрабатываем оптимальный алгоритм для класса моделей распространения влияния. Для общего K мы доказываем, что не существует алгоритма с полиномиальным временем, если для M K CP в хорошо известных моделях LT и IC не представлен и не представлен жадный алгоритм, основанный на алгоритме двух разделов. Мы также разрабатываем быстрый эвристический алгоритм с низкой вычислительной сложностью в случае, если социальная сеть очень большая.п= NпP=NP 3. Мы проводим моделирование в реальных социальных сетях, чтобы продемонстрировать практическую эффективность предложенных алгоритмов. Распространение влияния основано на хорошо известных моделях LT и IC, и экспериментальные результаты показывают, что значительно лучшие разделения могут быть получены с использованием наших алгоритмов, а не с использованием некоторых методов разделения сообщества, которые не специализируются на распространении влияния. 1.4 Организация бумаги Остальная часть этой статьи организована следующим образом. В разделе «Описание проблемы» мы даем справочную информацию, включая обозначения и определение проблемы. В разделе «Методы» мы представляем наши алгоритмы, а также теоретический анализ как предложенных алгоритмов, так и проблемы M K CP. В разделе «Результаты и обсуждение» мы показываем результаты моделирования в некоторых реальных социальных сетях. В разделе «Выводы» мы завершаем статью. 2 Описание проблемы В этом исследовании мы формулируем социальную сеть в виде простого ориентированного графа без петель, где узлы представляют пользователей, а ребра представляют отношения между пользователями. Сначала мы введем некоторые обозначения, а затем представим задачу M K CP, основанную на них. 1. Для социальной сети G обозначим через V = {1,2,…, n } множество узлов, а E = {( i , j )} - множество направленных ребер. Направленное ребро ( i , j ) означает, что существует вероятность распространения влияния между узлами i и j, где i - отправитель, а j - получатель. Для каждого узла i ∈ V обозначим через p ( i ) (0≤ p ( i ) ≤1) вероятность того, что узел iбудет способствовать распространению влияния или поделиться идеей с другими через социальную сеть. Например, в социальной сети Twitter p ( i ) должен соответствовать количеству твитов, которые я периодически публикую. Для каждого ребра ( i , j ) ∈ E через w ( i , j ) обозначим степень влияния от узла i до узла j , которая зависит от их близости и вероятности p ( i ) для узла i . 2. Обозначим через K количество сообществ. Обозначим через c i ∈ {1,2,…, K } идентификатор сообщества узла i . Обозначим через C k = { i | c i = k } множество узлов с идентификатором сообщества k (1≤ k ≤ K ). Для каждой пары узлов i и j в одном и том же наборе C k мы обозначим через ( ) вероятность того, что узел j получит влияние от узла i. пCk( я , j )pCk(i,j)0 ≤пCk( i , j ) ≤ 10≤pCk(i,j)≤1через распространение внутри сообщества C k . 3. Для сообщества C k и узла i ∈ C k мы обозначим через распространение влияния узла i внутри сообщества C k , т. . Для любого непустого подмножества D ⊆ C k мы обозначим через сумму распространения влияния внутри сообщества C k для каждого узла в D , т. . Для простоты обозначим σ ( X ) σ X ( X ) для сообщества σCk( я )σCk(i) σCk( i ) =∑j ∈ (Ck∖ я )пCk( я , j )σCk(i)=∑j∈(Ck∖i)pCk(i,j) σCk( D )σCk(D) σCk( D ) =∑i ∈ DσCk( я )σCk(D)=∑i∈DσCk(i) X, а в остальной части статьи мы называем σ (·) функцией распространения влияния для сообщества «·». Вероятность того, что узел j получит влияние от узла i, не только зависит от степени влияния w ( i , j ), но также зависит от топологии сети и модели распространения влияния. Например, в модели LT сумма влияния, которую получает узел j, может быть сформулирована как где N active ( j ) обозначает набор активных узлов вокруг j и . Распространение влияния происходит дискретными шагами. В любой момент времени t узел j ∈ V становится активным, когда∑i ∈Nактивный( j )ш ( я , j )∑i∈Nactive(j)w(i,j)∑i ∈Nактивный( j )ш ( я , J ) ≤ 1∑i∈Nactive(j)w(i,j)≤1∑i ∈Nактивный( j )w ( i , j ) ≥ λ ( j )∑i∈Nactive(j)w(i,j)≥λ(j) , где λ ( J ) представляет собой пороговое значение выбирается случайно равномерно между 0 и 1. Таким образом , в модели LT, для любого сообщества C к , вероятность того, что J в конечном счете активен , когда я изначально активен. В качестве примера, показанного на рисунке 1 , числа на краях и узлах обозначают степени влияния и случайные пороги. Предположим, что все узлы находятся в одном сообществе, а узел u является начальным, тогда все белые узлы (включая узел y ) могут быть активированы узлом u , потому что они могут быть активированы либо посредством u. пCk( я , j )pCk(i,j)или путями от u . Все черные узлы ( p , q и w ) не могут быть активированы узлом u , даже если q является прямым исходящим соседом u . Следовательно, в LT-модели зависит не только от степени влияния w ( i , j ). Далее мы дадим определения K -действительного дизъюнктного разбиения ( K -VDP) и проблемы M K CP.пCk( я , j )pCk(i,j) Рисунок 1 Рисунок 1 Иллюстрация распространения влияния. Полноразмерное изображение Определение 1. ( К - ВДП ). Учитывая график G ( V , E ) в качестве социальной сети, А К - действительное разбиению непересекающегося представляет собой набор из K множеств { C 1 , C 2 , ..., С К } , удовлетворяющие: (1) и (2) ∀ я ≠ J , C я ∩ C J = ∅ . ⋃Kk = 1(Ck) = V⋃k=1K(Ck)=V Пусть K - целое число, не меньшее 2. Согласно определению 1, K -VDP - это разбиение V на K непустых подмножеств, так что каждый узел находится в точном одном подмножестве. Обозначим функцию распространения влияния для K -VDP { C 1 , C 2 ,…, C K } через и мы хотим максимизировать f ( C 1 , C 2 ,…, C K ). Формальное определение M K CP дано в определении 2. ж(C1,C2,…,CK) =∑Kk = 1σ(Ck)f(C1,C2,…,CK)=∑k=1Kσ(Ck) Определение 2. ( MKCP ). Учитывая график G в качестве социальной сети, модели распространения влияния (такие , как IC или LT) и целое число K ≥2, Максимальная К -Community Partition (М К СР) является задача нахождения раздела из K подмножеств узлов ,п= {C1,C2, … ,CK}P={C1,C2,…,CK} максимизироватьтемакж(C1,C2, … ,CK) =∑Kk = 1σ(Ck){C1,C2, … ,CK}иша K - VDPfor G . maximizef(C1,C2,…,CK)=∑k=1Kσ(Ck)subjectto{C1,C2,…,CK}isaK−VDPforG. (1) Рассмотрим набор узлов V как единое сообщество, у нас есть ж⎛⎝⎜⎜⎧⎩⎨⎪⎪⎪⎪V⎫⎭⎬⎪⎪⎪⎪⎞⎠⎟⎟знак равно∑i ∈ V∑j ∈ V∖ { i }пV⎛⎝⎜⎜я , j⎞⎠⎟⎟. f({V})=∑i∈V∑j∈V∖{i}pV(i,j). Понятно, что при разделении социальной сети на два или более сообществ некоторые пары ( i , j ) будут разделены, и поэтому оба p V ( i , j ) и p V ( j , i ) должны быть удалены в сумме. распространения влияния. Кроме того, даже если узлы i и j разделены на одно и то же сообщество X , p X ( i , j ) может быть меньше p V ( i , j ), а p Х ( J , я ) может быть меньшечем р V ( J , я )потому что Х представляет собой подмножество V . Следовательно, влиятельное распространение между любой парой узлов i и j различно для разных разделов сообщества, независимо от того, находятся они в одном сообществе или нет. 3 метода 3.1 Оптимальный алгоритм для M2CP В этом подразделе мы представляем оптимальный алгоритм M2CP для класса моделей распространения влияния. Алгоритм основан на алгоритме Min Cut, предложенном в [ 46 ]. Прежде чем дать формальный алгоритм и его теоретический анализ, мы кратко обсудим разницу между проблемой Min Cut и проблемой M2CP. Минимальный разрез графа G - это набор ребер с наименьшим числом элементов (невзвешенный случай) или наименьшей суммой весов (взвешенный случай), которые разбивают Gна две части. Исходя из этого, для M2CP можно найти разрез, чтобы минимизировать распространение влияния между двумя частями. Однако максимизация суммы распространения влияния внутри каждого сообщества не эквивалентна минимизации распространения влияния через разные сообщества. На рисунке 2 показан пример. Есть восемь узлов, которые разделены на два сообщества C 1 = {1,2,3,4} и C 2.= {5,6,7,8}. Предположим, что серые дуги являются возможным распространением влияния. Рассмотрим узлы 7, 5 и 1 соответственно. Ясно, что влияние, полученное узлами 7 и 5, будет уменьшаться после разделения, поскольку узел 3 не может влиять на узел 7 и не может влиять на узел 5 через узел 7 косвенно. Влияние, полученное узлом 1, также уменьшается по следующим причинам: (1) узел 5 не может влиять на узел 1, (2) узел 7 не может влиять на узел 1 косвенно, и (3) узел 3 не может влиять на узел 1 через путь (3 → 7 → 5 → 1). Первые два вида распространения влияния - между узлами в разных сообществах, но последний - между узлами в одном сообществе. Следовательно, максимизация суммы распространения влияния внутри каждого сообщества - это не просто минимизация распространения влияния через разные сообщества. фигура 2 фигура 2 Пример M2CP. Полноразмерное изображение Учитывая социальную сеть, а также модель распространения влияния, наш алгоритм итеративно находит n −1 разделов и выбирает тот, у которого максимальное значение, в качестве окончательного результата. Вначале мы рассматриваем каждый узел i как единый набор и принимаем как набор всех наборов, где S i = { i }. Выберите произвольный набор и пусть . Затем мы итеративно добавляем оставшиеся наборы один за другим. Каждый раз добавляется набор S j с максимальным значением , где . Когда остается только один набор S l ,V= {S1,S2, … ,Sп}V={S1,S2,…,Sn} Sя∈ VSi∈VА= {Sя}A={Si} ς( А,Sj)ς(A,Sj)ς( А,Sj) = σ(A∪Sj)−σ(Sj)ς(A,Sj)=σ(A∪Sj)−σ(Sj) {v(A),v(V∖A)}{v(A),v(V∖A)} считается первым разделом, в котором определяется как набор узлов. Кроме того, последние два набора, не входящие , скажем, в S r и S l , объединяются как единый набор ( S r ∪ S l ) для вычисления следующего раздела. Алгоритм завершается, когда установлен только один. Псевдокод приведен в алгоритме 1.v(X)v(X) Вычислительная сложность AM2CP (алгоритм 1) зависит от временной сложности вычисления σ (·), которая дополнительно зависит от временной сложности вычисления распространения влияния для сообщества C k и всех пар ( i , j ) узлов в Это. В [ 15 ] Chen et al. доказать, что сложно вычислить точное распространение влияния в моделях LT и IC. Поэтому в этой работе оценивается с помощью моделирования MC. Предположим, у нас есть тренажер для оценки σ (·) за время τ . Следуя алгоритму 1, мы выполняем шаги (с 3 по 11) n −1 раз дляpCk(i,j)pCk(i,j) #P#PpCk(i,j)pCk(i,j)n −1 разбиение. Для каждого раздела мы жадно добавляем все наборы, в которые вызывается функция раз. Следовательно, общее время работы AM2CP равно .σ(⋅)O(n2)σ(·)O(n2)O(n3τ)O(n3τ) Далее мы покажем, что AM2CP является оптимальным решением для M2CP, когда функция распространения влияния сообщества σ (·) является супермодульной. Пусть S - конечное множество. Функция F : 2 S → R супер-модульные , если для любого B ⊂ A ⊂ S и ¯u ∉ A , σ(A∪{u})−σ(A)≥σ(B∪{u})−σ(B), σ(A∪{u})−σ(A)≥σ(B∪{u})−σ(B), (2) или, что то же самое, для любых B , A ⊂ S , σ(A∪B)+σ(A∩B)≥σ(A)+σ(B). σ(A∪B)+σ(A∩B)≥σ(A)+σ(B). (3) Теорема 1. Если функция распространения влияния σ (·) является супермодульной, AM2CP является оптимальным решением для M2CP. Доказательство На основе AM2CP каждый раз мы находим раздел , разделяющий два последних набора S r и S l , и объединяем эти два набора для следующего раунда. Чтобы показать теорему 1, достаточно показать, что имеет максимальное значение целевой функции среди всех разбиений, разделяющих S r и S l , где - это множество узлов в. Докажем это по индукции.P=(v(A),v(V∖A))P=(v(A),v(V∖A)) σ(v(A))+σ(v(V∖A))σ(v(A))+σ(v(V∖A)) v(X)v(X) Без потери общности, мы предполагаем, что добавляемые наборы расположены в следующем порядке: для раунда i, и пусть обозначает коллекцию первых j наборов, добавленных в раунд i . Тогда для любых и с j > 2 у нас есть потому что либо либо ∅ . Предположим, что для любых 2≤ k ′ < k , и с j > k ′Si1,Si2,…,Si|V|Si1,Si2,…,Si|V|AijAijS⊆Ai1S⊆Ai1SijSijσ(v(Ai2))+σ(Sij)≥σ(v(Ai2∖S))+σ(Sij∪v(S))σ(v(Ai2))+σ(Sij)≥σ(v(Ai2∖S))+σ(Sij∪v(S))v(S)v(S)Si1Si1σ(v(Aik′))+σ(Sij)≥σ(v(Aik′∖S))+σ(Sij∪v(S))σ(v(Aik′))+σ(Sij)≥σ(v(Aik′∖S))+σ(Sij∪v(S))S⊆Aik′−1S⊆Aik′−1SijSij. Далее мы покажем, что для любых и с j > k .σ(v(Aik))+σ(Sij)≥σ(v(Aik∖S))+σ(Sij∪v(S))σ(v(Aik))+σ(Sij)≥σ(v(Aik∖S))+σ(Sij∪v(S))S⊆Aik−1S⊆Aik−1SijSij Рассмотрим следующие два случая: (1) и (2) . Когда , у нас есть из-за предположения. Следовательно, потому что (1) , (2) и (3) σ (·) является супермодулярным.Sik−1∈SSik−1∈SSik−1∉SSik−1∉SSik−1∉SSik−1∉Sσ(v(Aik−2))+σ(Sij)≥σ(v(Aik−2∖S))+σ(Sij∪v(S))σ(v(Aik−2))+σ(Sij)≥σ(v(Aik−2∖S))+σ(Sij∪v(S))σ(v(Aik))+σ(Sij)≥σ(v(Aik∖S))+σ(Sij∪v(S))σ(v(Aik))+σ(Sij)≥σ(v(Aik∖S))+σ(Sij∪v(S))v(Aik)=v(Aik∖S)∪v(Aik−2)v(Aik)=v(Aik∖S)∪v(Aik−2)v(Aik−2∖S)=v(Aik∖S)∩v(Aik−2)v(Aik−2∖S)=v(Aik∖S)∩v(Aik−2) Когда , у нас есть из-за предположения, что . Поскольку σ (·) супермодулярно, мы имеем . В общем, у нас есть . Вдобавок у нас есть потому что в AM2CP . Поэтому в обоих случаях у нас есть . По индукции у нас есть для любого . Следовательно, раздел каждого раунда i в AM2CP имеет максимальное значение целевой функции среди всех разделов, разделяющих последние два набора. Каждый раз мы сравниваем с и объединяем два последних набора. СледовательноSik−1∈SSik−1∈Sσ(v(Aik−1))+σ(Sik)≥σ(v(S))+σ(Sik∪v(Aik−1∖S))σ(v(Aik−1))+σ(Sik)≥σ(v(S))+σ(Sik∪v(Aik−1∖S))σ(v(S))=σ(v(Aik−1)∖v(Aik−1∖S))σ(v(S))=σ(v(Aik−1)∖v(Aik−1∖S))σ(v(Aik−1)∪Sij)−σ(v(Aik−1))≥σ(v(S)∪Sij)−σ(v(S))σ(v(Aik−1)∪Sij)−σ(v(Aik−1))≥σ(v(S)∪Sij)−σ(v(S))σ(v(Aik∖S))+σ(Sij∪v(S))≤σ(v(Aik−1)∪Sij)+σ(Sik)σ(v(Aik∖S))+σ(Sij∪v(S))≤σ(v(Aik−1)∪Sij)+σ(Sik)σ(v(Aik−1)∪Sij)+σ(Sik)≤σ(v(Aik))+σ(Sij)σ(v(Aik−1)∪Sij)+σ(Sik)≤σ(v(Aik))+σ(Sij)Sik=argmaxSz∈V∖Aik−1(σ(Aik−1∪Sz)−σ(Sz))Sik=argmaxSz∈V∖Aik−1(σ(Aik−1∪Sz)−σ(Sz))σ(v(Aik))+σ(Sij)≥σ(v(Aik∖S))+σ(Sij∪v(S))σ(v(Aik))+σ(Sij)≥σ(v(Aik∖S))+σ(Sij∪v(S))σ(v(Ai|V|−1))+σ(Si|V|)>σ(v(Ai|V|−1∖S))+σ(Si|V|∪v(S))σ(v(Ai|V|−1))+σ(Si|V|)>σ(v(Ai|V|−1∖S))+σ(Si|V|∪v(S))S⊆Ai|V|−2S⊆Ai|V|−2PmaxPmaxPmaxPmax является оптимальным разбиением для задачи M2CP, когда функция распространения влияния σ (·) является супермодульной. Since AM2CP is an optimal solution if σ(·) is super-modular, we are interested in the influence propagation models in which the influence propagation function σ(·) is super-modular. Note that σ(·), in this paper, is different from the influence function defined in [14]. In this paper σ(X) is the sum of influence propagation within X for every node in X, i.e., σ(X)=∑i∈XσX(i)σ(X)=∑i∈XσX(i). In [14]σ(X) is the influence propagation of seed set X in the entire social network. We show the following lemma. Lemma 1 When the influence propagation model is LT, for any two communities: B⊂A, and a node u∉A, we have σ(A∪{u})−σ(A)≥σ(B∪{u})−σ(B). Proof. The influence propagation in the LT model, as shown in [14], can be simulated as a random process by flipping coins. Assume we have flipped all the coins in advance, then an edge is declared to be ‘live’ if the coin flip indicated an influence will be propagated successfully and it is declared blocked otherwise. A node j is influenced by a seed i if and only if there is a path of live edges from i to j. According to this principle, any simple path from i to j has a certain probability to be a live path. In [15], Chen et al. prove that for any node i, the influence propagation of i is equal to ∑sp∈SP(i)w(sp)∑sp∈SP(i)w(sp) where SP (i) is the set of all the simple paths starting from i and w(sp) is the probability that sp is a live path. Therefore, for a community X and a node i∈X, σX(i)=∑sp∈SPX(i)w(sp)σX(i)=∑sp∈SPX(i)w(sp) where SP X (i) is the set of simple paths starting from i in community X, and σ(X)=∑i∈XσX(i)σ(X)=∑i∈XσX(i) is the sum of probabilities for all the simple paths in X. Since for any two communities, B⊂A, the set of simple paths in B is a subset of the set of simple paths in A, we have σ(A)≥σ(B). Similarly, we have σ(A∪{u})−σ(A)≥σ(B∪{u})−σ(B) because σ(A∪{u})−σ(A) is the sum of probabilities of simple paths visit u exactly once in community (A∪{u}), and σ(B∪{u})−σ(B) is the sum of probabilities of simple paths visit u exactly once in community (B∪{u}) which is a subset of the former. Therefore, the influence propagation function σ(·) in the LT model is super-modular. Theorem 2. AM2CP is an optimal solution for M2CP in the LT model. Proof. The theorem follows directly from Theorem 1 and Lemma 1. By Lemma 1, we show that σ(·) is super-modular in the LT model. We next show that σ(·) in the IC model, however, is not super-modular. The description of IC model can be found in detail in [14]. Here we just give a counterexample. As an example shown in Figure 3, the weights are as follows: w(1,2)=w(1,3)=w(1,4)=1 and w(2,5)=w(3,5)=w(4,5)=0.5. According to the edges in Figure 3, nodes 2, 3, and 4 cannot influence each other and nodes 2, 3, 4, and 5 cannot influence node 1. Let community A={1,2,3,5} and community B={1,2,5}. So B is a subset of A. By direct computing, we have σ(A∪{4})−σ(A)=5.375−3.75=1.625 and σ(B∪{4})−σ(B)=3.75−2=1.75. Therefore, σ(A∪{4})−σ(A)<σ(B∪{4})−σ(B) which implies σ(·) is not super-modular in the IC model. Figure 3 фигура3 An example of the IC model. Full size image 3.2 Hardness In this subsection, we study the hardness of MK CP. We show that the MK CP problem, with arbitrary K, is NPNP-hard in the LT or IC model. Theorem 3. The MK CP problem is NPNP-hard in the LT model for general K. Proof. To prove Theorem 3, we do a polynomial time reduction from the Minimum K-Cut problem. The input of Minimum K-Cut is a simple graph G(V,E) without directions and an integer M. The objective is to find a set of at most M edges which when deleted, separate the graph into exactly K nonempty components. It is well known that the Minimum K-Cut problem is NPNP-hard for general K. Given a graph G(V,E) for the Minimum K-Cut problem, we construct a social network G′(V′,E′) as follows: (1) For each node i∈V, create a node i′ in V′. (2) For each edge (i,j)∈E, create two edges (i′,j′) and (j′,i′) in E′. (3) Let Δ denote the maximum degree in G and n denote the number of nodes in G. Assign weight w(i′,j′)=1(nΔ)2w(i′,j′)=1(nΔ)2 for all the edges (i′,j′)∈E′. It is clear that the reduction can be done in polynomial time. We next show that there is a K-Cut with M edges if and only if there is a K-VDP with f(P)≥2(|E|−M)(nΔ)2f(P)≥2(|E|−M)(nΔ)2. Assume there is a K-Cut with M edges, then graph G can be partitioned into K communities with |E|−M edges within the K communities. Consider the same partition in G′. The one-hop influence propagation is 2(|E|−M)(nΔ)22(|E|−M)(nΔ)2. Therefore, we have a K-VDP with f(P)>2(|E|−M)(nΔ)2f(P)>2(|E|−M)(nΔ)2 for G′. Conversely, assume there is a K-VDP for G′ with f(P)≥2(|E|−M)(nΔ)2f(P)≥2(|E|−M)(nΔ)2. It has been shown in [16] that for any nodes ∀i,j,l∈V, the probability of influence propagation from i to j via node l is equal to w(i,l)w(l,j) in the LT model. Therefore, a single two-hop influence propagation is 1(nΔ)41(nΔ)4. The number of two-hop simple paths for any node i′∈V′ is no more than Δ2. Therefore, the sum of two-hop influence propagation for every node in V′ is no more than nΔ2(nΔ)4=1n3Δ2nΔ2(nΔ)4=1n3Δ2. By direct computing, we have the sum of (r+1)-hop influence propagation is less than the sum of r-hop influence propagation for any node i. Since the length of simple paths is no more than n, we have the sum of multi-hop influence propagation for every node in V′ is less than 1(nΔ)21(nΔ)2. This implies that f(P)≥2(|E|−M)(nΔ)2f(P)≥2(|E|−M)(nΔ)2 if and only if the one-hop influence propagation is no less than 2(|E|−M)(nΔ)22(|E|−M)(nΔ)2. Therefore, the same partition in G is a K-Cut with at most M edges. In sum, we prove Theorem 3. Theorem 4. The MK CP problem is NPNP-hard in the IC model for general K. Proof. To prove Theorem 4, we can do the same reduction as the one in the proof of Theorem 3, i.e., assign uniform weight 1(nΔ)21(nΔ)2 on all the edges. It can be shown by induction that the sum of (r+1)-hop influence propagation a node i received is less than the sum of r-hop influence propagation it received for any node i∈V′ in the IC model. Therefore, by a similar argument, we have the sum of multi-hop influence propagation received for every node i∈V′ is less than the edge weight. Therefore, there exists a K-Cut with M edges if and only if there is a K-VDP with f(P)≥2(|E|−M)(nΔ)2f(P)≥2(|E|−M)(nΔ)2. The proofs of Theorems 3 and 4 are nothing but assign specific weights to make the multi-hop influence propagation negligible. It is intuitive that the general MK CP problem is even harder when multi-hop influence propagation is not negligible. 3.3 Heuristic algorithm for MK CP In this subsection, we present two heuristic algorithms for MK CP. As mentioned in ‘Related work’ section in the literature, there are mainly four categories of methods for community partition: hierarchy-based methods, spectrum-based methods, density-based methods, and modularity-based methods. In our point of view, spectrum-based methods, density-based methods, and modularity-based methods are not suitable for MK CP. In spectrum-based methods, communities are partitioned by studying the adjacency matrix which cannot reflect the information of influence propagation. In density-based methods, communities are defined as areas of higher density than the remainder of the data set. Therefore, this category of methods requires the location knowledge of nodes which cannot be formulated in our MK CP problem. In modularity-based methods, the objective of community partition is only to maximize the global modularity score. Therefore, all the three categories of methods cannot be applied for MK CP and we focus on hierarchy-based methods. Вообще говоря, иерархическое разделение сообществ - это метод построения иерархии сообществ. Есть две стратегии иерархического разделения. Один разделен, а другой объединен . Разделение - это подход сверху вниз, т. Е. Все узлы начинаются в одном сообществе, а разделение выполняется в одном из сообществ рекурсивно. И наоборот, слияние - это восходящий подход, т. Е. Каждый узел начинается в отдельном сообществе, а пары сообществ рекурсивно сливаются в новое сообщество. Для типичных задач иерархического разделения сообщества необходимо выполнить n -1 разделений (или, соответственно, слияний), чтобы построить иерархию, где n - количество узлов. Но для задачи M K CP нам понадобится только K−1 разбивает или n - K объединяет соответственно, чтобы получить K -VDP. Мы будем жадно определять разбиения и слияния. Алгоритм Split запускается путем рекурсивного вызова AM2CP и каждый раз разделяет сообщество X на два сообщества X 1 и X 2 с минимальным значением σ ( X ) - ( σ ( X 1 ) + σ ( X 2 )). Псевдокод дается в алгоритме 2. Алгоритм слияния запускается путем случайного выбора сообщества X каждый раз и поиска другого сообщества Yчтобы максимизировать значение σ ( X ∪ Y ) - ( σ ( X ) + σ ( Y )). Псевдокод приведен в алгоритме 3. В общем случае время работы сплита с полным перебором требует экспоненциального времени. Однако, когда σ (·) является супермодульным, мы можем применить AM2CP для определения и для каждого C z, что требует только времени . Теперь рассмотрим вычислительную сложность SAM K CP (алгоритм 2). Чтобы избежать дублирования вычислений, мы можем сохранить оптимальное разделение для каждого сообщества и применить AM2CP как к и к на шаге 4, чтобы получить их оптимальные разделы. Тогда общее время работы SAM K CP равно когда σCz1Cz1Cz2Cz2 О( |Cz|3τ)О(|Cz|3τ)Cz1Cz1Cz2Cz2О( Kп3τ)О(Kп3τ)(·) Является супермодульным. In step 4 of MAMK CP (Algorithm 3), in order to maximize the marginal gain, we have to compute σ(C i ∪C j ) for all the communities Cj∈ PCj∈п, thus, MAMK CP requires О(п2τ)О(п2τ) time to obtain a K-VDP when n is large and K is small. The computational complexity of SAMK CP is even higher. Therefore, they may be not suitable for large social networks. To improve the running time performance, here we provide an alternative merge strategy for implementing MAMK CP. Instead of merging the communities with the maximum marginal gain, in step 4 we estimate the influence propagation of C i through the entire graph, i.e., σ V (C i ), and then compute the average influence received by C j from C i , which is defined as ∑l∈Ci∑r∈CjpV(l,r)|Cj|∑l∈Ci∑r∈CjpV(l,r)|Cj|, for all the communities C j ≠C i . This can be done by simply accumulating p V (l,r) for each community C j when we computing σ V (C i ). Finally, we merge C i with a community with the highest average received influence. In such a way, a merge can be done in O(τ) time. The overall running time of MAMK CP is only O(nτ)O(nτ). According to the complexity analysis, MAMK CP is better than SAMK CP in terms of the running time performance. For some large social networks, we can apply the simplified version of MAMK CP which requires only linear time. In terms of the partition quality, intuitively, SAMK CP is better than MAMK CP because it considers the global optimization (top-down approach) each time and MAMK CP considers the local optimization (bottom-up approach). We will demonstrate their performance through simulation in the next section. 4 Results and discussion In this section, we carry out experiments over real-world social networks. The influence propagation is based on the well-known LT and IC models, and we run MC simulation to estimate the influential propagation function σ(·). We begin by describing the algorithms, data sets, and experimental settings in ‘Algorithm,’ ‘Data set,’ and ‘Experiment setting’ sections, respectively, and then discuss the experimental results in ‘Experiment result’ section. 4.1 Algorithm In addition to the proposed algorithms, (SAMK CP, Algorithm 2) and (MAMK CP, Algorithm 3), we also implement two classic community partition algorithms for comparison purposes. One is a Modularity-based Algorithm (MODUA) proposed in [47] and the other is a Spectrum-based Algorithm (SPECA) proposed in [48]. Given a graph G, MODUA finds communities by optimizing the modularity score locally and it terminates until a maximal modularity score is obtained. Therefore, MODUA cannot partition G into a given number K of communities. While SPECA is flexible for the number K of communities, it partitions a graph iteratively into K communities by minimizing the general cut each time according to the adjacent matrix. To the best of our knowledge, we do not find any algorithm which is designed for disjoint community partition with the objective of maximizing the influence propagation within each community. In addition, we do not find any density-based algorithm that can be applied to our MK CP problem. 4.2 Data set We conduct simulation on three real-world social networks as follow: (1) NetHEPT: taken from the co-authorship network in ‘High Energy Physics (Theory)’ section (from 1991 to 2003) of arXiv (http://arXiv.org). The nodes in NetHEPT denote the authors, and the edges represent the co-authorship. HetHEPT has 15,229 nodes and 31,376 edges. (2) NetEmail: taken from the email interchange network in University of Rovira i Virgili (Tarragona). The nodes in NetEmail denote the members in the university, and the edges represent email interchanges among the members (the data set is available at http://deim.urv.cat/~alephsys/data.php). NetEmail has 1,133 nodes and 10,902 edges. (3) NetCLUB: taken from the relationship network in Zachary’s Karate club network, which is described by Wayne Zachary in [49]. NetCLUB has 34 nodes and 78 edges. 4.3 Experiment setting In this study, we assume that the influential degree from nodes i to j depends on the closeness of their relationship and the probability p(i) for node i where p(i), as defined in Problem description’ section, is the probability that node i would produce an influence propagation or would share knowledge with others. We apply the method proposed in [14] to estimate the closeness c(i,j) between i and j. Let degin(j) denote the in-degree of node j, then c(i,j)=e(i,j)/ degin(j), where e(i,j) denotes the number of edges from i to j. Due to the lack of ground truth, we independently assign uniform random 0.1%, 1%, and 10% to sharing probabilities p(i) for all the nodes i. Then we assume ∀(i,j)∈E, i has a chance of w⎛⎝⎜i,j⎞⎠⎟=p(i)e(i,j)degin(j)w(i,j)=p(i)e(i,j)degin(j) to influence j. 4.4 Experiment result Сначала мы оцениваем производительность наших алгоритмов на NetCLUB. В алгоритме SAM K CP или MAM K CP σ (·) вычисляется путем выполнения моделирования MC 1000 раз и получения среднего значения. Хотя AM2CP не является оптимальным решением в модели IC, мы по-прежнему применяем его в разбиениях при моделировании модели IC, чтобы повысить эффективность вычислений. Поскольку MODUA не является гибким для количества сообществ, мы сначала применяем MODUA, чтобы получить раздел NetCLUB, а затем применяем наши алгоритмы и SPECA для разделения NetCLUB на такое же количество сообществ. На рисунках 4 и 5 показаны экспериментальные результаты для моделей LT и IC соответственно. NetCLUB разделен на четыре сообщества. С точки зрения распространения влияния оба SAMK CP и MAM K CP лучше, чем MODUA и SPECA. SAM K CP превосходит MODUA и SPECA примерно на 40% и 70% соответственно. Кроме того, из рисунков 4 и 5 видно, что распространение влияния каждого раздела постепенно и линейно увеличивается с увеличением времени моделирования, что отражает надежность экспериментальных результатов. Рисунок 4 фигура 4 Результаты экспериментов на NetCLUB в модели LT. Полноразмерное изображение Рисунок 5. цифра 5 Результаты экспериментов на NetCLUB в модели IC. Полноразмерное изображение Во втором эксперименте мы сравниваем MAM K CP с MODUA и SPECA в NetEmail. SAM K CP удален из-за его высокой вычислительной сложности. На рисунках 6 и 7 показаны результаты экспериментов. Сеть разделена на 88 сообществ. MAM K CP имеет максимальную сумму распространения влияния. По сравнению с MAM K CP и MODUA эффективность СПЕКА оставляет желать лучшего. Распространение влияния внутри раздела SPECA примерно в два раза меньше, чем у MAM K CP, и примерно в один раз меньше, чем у MODUA. Рисунок 6 фигура6 Результаты экспериментов по NetEmail в модели LT. Полноразмерное изображение Рисунок 7 рисунок 7 Результаты экспериментов по NetEmail в модели IC. Полноразмерное изображение В последнем эксперименте мы сравниваем MAM K CP с MODUA и SPECA на NetHEPT. Поскольку в этой сети 15 229 узлов и 31 376 ребер, мы используем упрощенную версию MAM K CP. На рисунках 8 и 9 показаны результаты экспериментов. Сеть разделена на 1820 населенных пунктов. MAM K CP по-прежнему лучше, чем MODUA и SPECA, но разрыв между MAM K CP и MODUA в этом эксперименте меньше, чем во втором эксперименте. Это согласуется с нашей интуицией в том, что упрощенный MAM KCP имеет меньшую вычислительную сложность, но также имеет некоторую потерю производительности. По результатам трех экспериментов можно сделать вывод, что предложенные алгоритмы лучше, чем методы на основе модульности и спектра для поиска сообществ с точки зрения распространения влияния. Рисунок 8 фигура 8 Результаты экспериментов по NetHEPT в модели LT. Полноразмерное изображение Рисунок 9 рисунок9 Результаты экспериментов по NetHEPT в модели IC. Полноразмерное изображение 5. Выводы Community partition and influence propagation are important problems in social networks. In this paper, we investigate the Maximum K-Community Partition (MK CP) problem to maximize the sum of influence propagation within each community. We analyze the problem both theoretically and practically. Especially we show that the M2CP problem can be solved efficiently for a class of influence propagation models. In addition, we prove that the MK CP problem is NпNп-hard in the well-known LT and IC models for general K. We also develop two heuristic algorithms and demonstrate their efficiency through simulation on real-world social networks. Мы считаем, что это исследование полезно для решения проблем распространения влияния. В будущих исследованиях мы планируем расширить нашу работу до задачи максимизации влияния, чтобы выбрать наиболее влиятельные узлы на основе сообществ, основанных на влиянии. Кроме того, мы изучим возможные применения сообществ, основанных на влиянии, в социальных сетях. использованная литература 1. Боллобас Б: Современная теория графов . Спрингер Верлаг, Нью-Йорк; 1998 г. Книга МАТЕМАТИКА Google ученый 2. Гирван М., Ньюман МЭЙ: Структура сообщества в социальных и биологических сетях. Proc. Natl. Акад. Sci 2002, 99 (12): 7821–7826. 10.1073 / pnas.122653799 MathSciNet Статья МАТЕМАТИКА Google ученый 3. Luxburg, U: Учебное пособие по спектральной кластеризации. Стат. Comput. 17, 395–416 (2007). 4. Каннан Р., Вемпала С., Ветта А. О кластеризации: хорошие, плохие и призрачные. J. ACM 2004, 51 (3): 497–515. 10.1145 / 990308.990313 MathSciNet Статья МАТЕМАТИКА Google ученый 5. Манкоридис, С., Митчелл, Б.С., Роррес, К. Использование автоматической кластеризации для создания системной организации высокого уровня исходного кода. В: Материалы 6-го Международного семинара по пониманию программ, Искья, Италия, 24–26 июня 1998 г. , стр. 45–53 (1998). 6. Ньюман, М., Гирван, М.: Поиск и оценка структуры сообщества в сетях. Phys. Ред. E. 69, 026113 (2004). 7. Уайт, С., Смит, П.: Спектральный кластерный подход к поиску сообществ в графах. В: SDM'05: Материалы 5-й Международной конференции SIAM по интеллектуальному анализу данных , стр. 76–84 (2005). 8. Ньюман М: Модульность и структура сообщества в сетях. Proc. Natl. Акад. Sci. США 2006, 103 (23): 8577–8582. 10.1073 / pnas.0601602103 Статья Google ученый 9. Браун, Дж., Рейнеген, П: Социальные связи и устное обращение к специалистам. J. Consum. Res. 14, 350–362 (1987). 10. Гольденберг Дж., Либай Б., Мюллер Э: Использование комплексного системного анализа для продвижения развития теории маркетинга: моделирование эффектов неоднородности на рост новых продуктов с помощью стохастических клеточных автоматов. Акад. Рынок. Sci. Ред. 2001 г., 9 (3): 1–18. Google ученый 11. Гольденберг, Дж., Либай, Б., Мюллер, Э: Разговор о сети: сложные системы рассматривают основной процесс молвы. Рынок. Lett. 12. С. 211–223 (2001). 12. Ричардсон, М., Домингос, В.: Майнинг сайтов по обмену знаниями для вирусного маркетинга, Эдмонтон, Альберта, Канада, 23–26 июля 2002 г., стр. 61–70. KDD (2002). 13. Домингос, П., Ричардсон, М.: Анализ сетевой ценности клиентов, Сан-Франциско, Калифорния, США, 26–29 августа 2001 г., стр. 57–66. KDD (2001). 14. Кемпе Д., Кляйнберг Дж. М., Тардос Э .: Максимальное распространение влияния через социальную сеть. В материалах 9-й Международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных . ACM, Нью-Йорк; 2003 г. Google ученый 15. Чен, В., Юань, Чжан, Л.: Масштабируемая максимизация влияния в социальных сетях в рамках линейной пороговой модели. В: Материалы 10-й Международной конференции IEEE по интеллектуальному анализу данных, Сидней, Австралия, 14–17 декабря 2010 г. , стр. 88–97 (2010). 16. Chen W, Wang C, Wang Y: Масштабируемая максимизация влияния для распространенного вирусного маркетинга в крупных социальных сетях. В материалах 16-й Международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных . ACM, Нью-Йорк; 2010 г. Google ученый 17. Wang Y, Cong G, Song G, Xie K: жадный алгоритм на основе сообщества для добычи топ-k влиятельных узлов в мобильных социальных сетях. В материалах 16-й Международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных (KDD'10) . ACM, Нью-Йорк; 2010 г. Google ученый 18. Радикки Ф., Кастеллано С., Чеккони Ф., Лорето В., Паризи Д.: Определение и идентификация сообществ в сетях. Proc. Natl. Акад. Sci. США 2004 г., 101 (9): 2658–2663. 10.1073 / pnas.0400054101 Статья Google ученый 19. Hu, Y, Chen, H, Zhang, P, Zhang, P, Li, M, Di, Z, Fan, Y: сравнительное определение сообщества и соответствующий алгоритм идентификации. Phys. Ред. E. 78, 026121 (2008). 20. Вайс Р.С., Якобсон Э .: Метод анализа структуры сложных организаций. Являюсь. Социол. Ред. 1955 г., 20 (6): 661–668. 10.2307 / 2088670 Статья Google ученый 21. Boettcher, S, Percus, AG: Экстремальная оптимизация для разбиения графа. Phys. Ред. E. 64, 026114 (2001). 22. Пункт A, Newman MEJ, Moore C: поиск структуры сообщества в очень больших сетях. Phys. Ред. E 2004, 70 (6): 066111. 10.1103 / PhysRevE.70.066111 Статья Google ученый 23. Ньюман, MEJ: Быстрый алгоритм для определения структуры сообщества в сетях. Phys. Ред. E. 69, 066133 (2004). 24. Вакита К., Цуруми Т. Определение структуры сообщества в мегамасштабных социальных сетях. В материалах 16-й Международной конференции по всемирной паутине, WWW'07 . ACM, Нью-Йорк; 2007 г. Google ученый 25. Гимера Р., Пардо МС: ЛВС: модульность от флуктуаций случайных графов и сложных сетей. Phys. Ред. E 2004, 70 (2): 025101. 10.1103 / PhysRevE.70.025101 Статья Google ученый 26. Массен, К.П., Дой, JPK: Определение сообществ в энергетических ландшафтах. 71, 046101 (2005). 27. Дуч Дж., Аренас А. Обнаружение сообществ в сложных сетях с использованием экстремальной оптимизации. Phys. Ред. E 2005, 72 (2): 027104. 10.1103 / PhysRevE.72.027104 Статья Google ученый 28. Холланд Дж. Х .: Адаптация в естественных и искусственных системах . Массачусетский технологический институт, Кембридж; 1992 г. Google ученый 29. Pizzuti C: Обнаружение сообществ в социальных сетях с помощью генетических алгоритмов. В материалах 10-й ежегодной конференции по генетическим и эволюционным вычислениям, GECCO'08 . ACM, Нью-Йорк; 2008 г. Google ученый 30. Фортунато С., Бартелеми М.: Предел разрешения при обнаружении сообщества. Proc. Natl. Акад. Sci. США 2007, 104 (1): 36–41. 10.1073 / pnas.0605965104 Статья Google ученый 31. Чжан Х, Ли З, Ван Р, Ван И: комбинаторная модель и алгоритм для глобального поиска структуры сообщества в сложных сетях. J. Combin. Оптим 2010, 23 (4): 425–442. 10.1007 / s10878-010-9356-0 MathSciNet Статья Google ученый 32. Фортунато, S: Обнаружение сообществ в графах. Phys. 2010. Т. 486. С. 75–174. 33. Гертлер, М: Кластеризация. В: Брандес, У, Эрлебах, Т. (ред.) Сетевой анализ: методологические основы , стр. 178–215. Спрингер (2005). 34. Ланчинетти, А., Фортунато, С.: Алгоритмы обнаружения сообщества: сравнительный анализ. Phys. Ред. E. 80, 056117 (2009). 35. Шеффер С: Кластеризация графов. Comput. Sci. Ред. 2007, 1 (1): 27–64. 10.1016 / j.cosrev.2007.05.001 MathSciNet Статья МАТЕМАТИКА Google ученый 36. Andersen, R, Chung, F, Lang, K: Local graph partitioning using PageRank vectors. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, USA, 21–24 October 2006, pp. 475–486 (2006). 37. Leicht EA, Newman MEJ: Community structure in directed networks. Phys. Rev. Lett 2008,100(11):118703. 10.1103/PhysRevLett.100.118703 Article Google Scholar 38. Leskovec, J, Krause, A, Guestrin, C, Faloutsos, C, VanBriesen, J, Glance, N: Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, CA, USA, 12–15 August 2007, pp. 420–429 (2007). 39. Кимура, М., Сайто, К.: Управляемые модели распространения информации в социальных сетях, стр. 259–271, PKDD (2006). 40. Кимура, М., Сайто, К., Мотода, Х: Эффективная оценка функций влияния для модели SIS в социальных сетях. В: Материалы 21-й Международной совместной конференции по искусственному интеллекту, Пасадена, Калифорния, США, 11–17 июля 2009 г. , стр. 2046–2051 (2009). 41. Ли, Х., Бхоумик, С., Сан, А: CINEMA: жадный алгоритм с учетом конформности для максимизации влияния в социальных сетях онлайн, стр. 323–334. ЕАБР (2013). 42. Галстян А., Мусоян В., Коэн П. Максимальное распространение влияния в сетях со структурой сообщества. Phys. Ред. E 2009, 79 (5): 056102. 10.1103 / PhysRevE.79.056102 Статья Google ученый 43. Nguyen, NP, Yan, G, Thai, MT, Eidenbenz, S: Сдерживание распространения дезинформации в социальных сетях. WebSci, 2012, стр. 213–222. 44. Динь, Теннесси, Сюань, Й, Тай, Монтана: На пути к социально-ориентированной маршрутизации в динамических коммуникационных сетях. IPCCC, стр. 161–168 (2009). 45. Белак В., Лам С., Хейс К. Ориентация на онлайн-сообщества для максимального распространения информации. В материалах семинара WWW по динамике майнинга социальных сетей . Лион, Франция; 2012 г. Google ученый 46. Stoer M, Wagner F: простой алгоритм минимального сокращения. J. ACM 1997, 44 (4): 585–591. 10.1145 / 263867.263872 MathSciNet Статья МАТЕМАТИКА Google ученый 47. Блондель, В., Гийом, Дж., Ламбьот, Р., Лефевр, Э: Быстрое развертывание сообществ в больших сетях. J. Stat. Мех. Теор. Опыт (2008). 48. Диллон, И, Гуан, Й, Кулис, Б.: быстрый многоуровневый алгоритм на основе ядра для кластеризации графов. В: Материалы 11-го заседания ACM SIGKDD, Чикаго, Иллинойс, США, 21–24 августа 2005 г. , стр. 629–634 (2005). 49. Захари, В .: Модель информационного потока для конфликта и расщепления в малых группах. J. Anthrop. Res. 33, 452–73 (1977). Скачать ссылки Благодарности Эта исследовательская работа частично поддержана Национальным научным фондом США в рамках грантов NSF 1137732 и NSF 1241626. Информация об авторе Принадлежности Центр NSF по исследованию сложных сетей, Южный Техасский университет, 3100 Cleburne Street, Хьюстон, Техас, 77004, США Зайсинь Лу и Вэй Ли Департамент компьютерных наук Техасского университета в Далласе, 800 W. Campbell Road, Richardson, TX, 75080, USA Юцин Чжу и Вейли Ву Департамент компьютерных наук Техасского южного университета, 3100 Cleburne Street, Хьюстон, Техас, 77004, США Вэй Ли Департамент компьютерных наук, Университет Джорджа Вашингтона, 2121 Eye Street NW, Вашингтон, округ Колумбия, 20052, США Сючжэнь Чэн Автор, ответственный за переписку Переписка с Зайсинь Лу . Дополнительная информация Конкурирующие интересы Авторы заявляют, что у них нет конкурирующих интересов. Вклад авторов ZL и YZ сформулировали задачу, а также разработали и реализовали алгоритм. WL, WW и XC внесли свой вклад в теоретическую часть разработки алгоритмов и организовали это исследование. Все авторы прочитали и одобрили окончательную рукопись. Оригинальные отправленные авторами файлы изображений Ниже приведены ссылки на исходные файлы изображений, представленные авторами. Оригинальный файл авторов для рисунка 1 Оригинальный файл авторов для рисунка 2 Оригинальный файл авторов для рисунка 3 Оригинальный файл авторов для рисунка 4 Оригинальный файл авторов к рисунку 5 Оригинальный файл авторов к рисунку 6 Оригинальный файл авторов к рисунку 7 Оригинальный файл авторов к рисунку 8 Оригинальный файл авторов к рисунку 9 Оригинальный файл авторов к рисунку 10 Оригинальный файл авторов к рисунку 11 Оригинальный файл авторов к рисунку 12 Права и разрешения Открытый доступ Эта статья распространяется в соответствии с условиями Международной лицензии Creative Commons Attribution 4.0 ( https://creativecommons.org/licenses/by/4.0 ), которая разрешает использование, копирование, адаптацию, распространение и воспроизведение на любом носителе и любом формате. , при условии, что вы должным образом указываете на оригинального автора (авторов) и источник, предоставляете ссылку на лицензию Creative Commons и указываете, были ли внесены изменения. Отпечатки и разрешения Об этой статье Подтвердите валюту и подлинность через CrossMark Цитировать эту статью Лу З., Чжу Ю., Ли В. и др. Разделение сообщества на основе влияния для социальных сетей. Compu Social Networls 1, 1 (2014). https://doi.org/10.1186/s40649-014-0001-4 Скачать цитату Полученный 31 декабря 2013 г. Принято 07 мая 2014 Опубликовано 15 октября 2014 г. DOI https://doi.org/10.1186/s40649-014-0001-4 Поделиться этой статьей Любой, с кем вы поделитесь следующей ссылкой, сможет прочитать этот контент: Получить ссылку, которой можно поделиться Предоставлено инициативой по обмену контентом Springer Nature SharedIt Ключевые слова Распространение влияния Раздел сообщества NP $ \ mathcal {NP} $ - сложно Скачать PDF Разделы Цифры использованная литература Абстрактный 1. Фон 2 Описание проблемы 3 метода 4 Результаты и обсуждение 5. Выводы использованная литература Благодарности Информация об авторе Дополнительная информация Оригинальные отправленные авторами файлы изображений Права и разрешения Об этой статье Рекламное объявление Поддержка и контакты Вакансии Редактирование языков для авторов Научное редактирование для авторов Оставить отзыв Условия и положения Заявление о конфиденциальности Доступность Печенье Следуйте за SpringerOpen Страница SpringerOpen в Твиттере Страница SpringerOpen в Facebook Используя этот сайт, вы соглашаетесь с нашими Условиями , Калифорния Заявление о конфиденциальности , о конфиденциальности и Cookies политики. Управление файлами cookie / Не продавать мои данные, которые мы используем в Центре предпочтений. Springer Nature © 2021 BioMed Central Ltd, если не указано иное. Часть Springer Nature . Цифровые коммуникации и сети Том 7, выпуск 1 , февраль 2021 г. , страницы 131-139 Цифровые коммуникации и сети Выявление влиятельных узлов в социальных сетях через структуру сообщества и влияние на разницу в распределении Ссылки авторов открывают панель наложенияЦзуфань Чжан а б в Селян Ли а б в Чэньцюань Гань а б в Показать больше Добавить в Mendeley Делиться Cite https://doi.org/10.1016/j.dcan.2020.04.011Получите права и контент Под лицензией Creative Commons лицензииоткрытый доступ Абстрактный Данная статья направлена ​​на эффективное решение проблемы максимизации влияния в социальных сетях. Для этого предлагается метод максимизации влияния, который может идентифицировать влиятельные узлы через структуру сообщества и разницу в распределении влияния. Во-первых, разрабатывается подход к обнаружению сообществ на основе внедрения сети, при котором социальная сеть делится на несколько качественных сообществ. Во-вторых, решение максимизации влияния состоит из стадии кандидата и стадии жадности. Этап-кандидат состоит в том, чтобы выбрать узлы-кандидаты изнутри и на границе каждого сообщества с помощью эвристического алгоритма, а этап жадности - определить исходные узлы с наибольшим приращением предельного влияния из набора кандидатов с помощью субмодульного алгоритма Greedy на основе свойств. алгоритм. Наконец-то, Предыдущая статья в выпускеСледующая статья в выпуске Ключевые слова Социальная сетьОбнаружение сообществаМаксимизация влиянияВстраивание сетиРазница в распределении влияния Извините, что-то пошло не так. Пожалуйста, попробуйте еще раз и убедитесь, что куки включены Веб-сайты IEEE размещают файлы cookie на вашем устройстве, чтобы вам было удобнее работать с ними. Используя наши веб-сайты, вы соглашаетесь на размещение этих файлов cookie. Чтобы узнать больше, прочтите нашиПолитика конфиденциальности. Принять и закрыть Перейти к основному содержанию IEEE.org IEEE Xplore IEEE-SA IEEE Spectrum Больше сайтов ПОДПИСЫВАТЬСЯ Корзина Создать аккаунт Личный вход Логотип IEEE Xplore - ссылка на главную Просматривать Мои настройки Помощь Институциональный вход Логотип IEEE - ссылка на главную страницу сайта IEEE РАСШИРЕННЫЙ ПОИСК Journals & Magazines >IEEE Access >Volume: 8 Измерение чувствительного ко времени и тематического влияния в социальных сетях с помощью LSTM и самовнимания Издатель: IEEE Цитировать это PDF Ченг Чжэн; Цинь Чжан ; Годун Лонг ; Чэнци Чжан ; Шон Д. Янг ; Вэй Ван Все авторы 5 Бумага Цитаты 876 Полный Текстовые представления Открытый доступ Комментарии) Под лицензией Creative Commons Абстрактный Разделы документа Я. Вступление II. Предварительные мероприятия III. Структура TTIM IV. Эксперименты В. Связанных с работой Показать полную схему Авторы Цифры использованная литература Цитаты Ключевые слова Метрики СМИ Сноски Абстрактный: Измерение влияния в социальных сетях жизненно важно для различных реальных приложений, таких как интернет-маркетинг и политические кампании. В этой статье мы исследуем проблему измерения чувствительного ко времени и тематического влияния на основе потоковых текстов и динамических социальных сетей. Влияние пользователя может быстро меняться в ответ на новое событие и варьироваться по разным темам. Например, политическое влияние Дугласа Джонса резко возросло после победы на специальных выборах в Алабаме, а затем быстро уменьшилось после недели выборов. Однако в тот же период влияние Дугласа Джонса на спорт оставалось низким. Большинство существующих подходов могут моделировать влияние только на основе статических структур социальных сетей и тематических распределений. Более того, Поскольку популярные службы социальных сетей включают в себя множество функций для связи между пользователями, разнотипные взаимодействия затрудняют изучение ролей, которые различные взаимодействия играют при распространении информации. Чтобы решить эти проблемы, мы предлагаем метод измерения влияния с учетом времени и тематики (TTIM) для совместного моделирования потоковых текстов и динамических социальных сетей. Мы моделируем процесс распространения влияния с помощью механизма самовнимания, чтобы узнать вклад различных взаимодействий и отслеживать динамику влияния с помощью адаптивной к матрице долговременной краткосрочной памяти. Насколько нам известно, это первая попытка измерить влияние, зависящее от времени и конкретной темы. Более того, Модель TTIM может быть легко адаптирована для поддержки онлайн-обучения, которое требует постоянного времени на обучение вновь поступающим данным для каждой временной метки. Мы всесторонне оцениваем предлагаемую модель TTIM на пяти наборах данных из Twitter и Reddit. Результаты экспериментов демонстрируют многообещающую производительность по сравнению с современными моделями анализа социального влияния и потенциал TTIM в визуализации динамики влияния и распределения тем. Опубликовано в: IEEE Access ( том: 8 ) Страницы: 82481 - 82492 Дата публикации: 06 мая 2020 г. Электронный ISSN: 2169-3536 Идентификатор PubMed: 32577335 Регистрационный номер INSPEC : 19658975 DOI: 10.1109 / ACCESS.2020.2991683 Издатель: IEEE Финансирующее агентство: Чтобы измерить влияние, зависящее от времени и конкретной темы в социальных сетях, мы предлагаем неконтролируемую модель, которая называется моделью измерения влияния с учетом времени и темы (TTIM). TTIM состоит из сети влияния и внимания и матрично-адаптивной долговременной кратковременной памяти, которую можно совместно тренировать для автоматизации функции. Цель обучения без учителя может управлять системой обучения без надзора с земли. Для измерения влияния в социальных сетях, зависящего от времени и конкретной темы, мы предлагаем неконтролируемую модель, которая называется «Измерение влияния с учетом времени и конкретной темы» ... Подробнее Скрыть аннотацию полностью CCBY - IEEE не является владельцем авторских прав на этот материал. Следуйте инструкциям на https://creativecommons.org/licenses/by/4.0/, чтобы получить полнотекстовые статьи и условия в документации API.https : // creativecommons . org / licenses / by / 4 . 0 / для получения полнотекстовых статей и положений в документации API. РАЗДЕЛ I.Вступление Влияние социальной сети относится к способности пользователя изменять чувства, отношения или поведение других пользователей в сети [1] - [2] [3] . Измерение влияния стало важной задачей во многих областях, таких как интернет-маркетинг [4] , [5] и политические кампании [6] . Из-за своей практической важности измерение социального влияния привлекает растущий исследовательский интерес [7] - [8] [9] [10].. В этой статье мы изучаем проблему измерения влияния во временных социальных сетях: с учетом потоковой передачи сообщений и интерактивных действий цель состоит в том, чтобы смоделировать динамику влияния пользователей и найти распределение влияния по различным темам. Влияние пользователя со временем меняется [8] . Человек может стать влиятельным в течение определенного периода благодаря определенному событию. Одним из примеров является Дуглас Джонс , 1 нынешний сенатор США в штате Алабама. 12 декабря 2017 года Джонс выиграл внеочередные выборы и стал первым демократом, получившим место в Сенате Алабамы с 1992 года. Благодаря этой победе политическое влияние Дугласа Джонса резко возросло в период выборов, а затем быстро исчезло после выборов. Это отражено в оценках влияния, показанных на Рисунке 1 . Красная звезда отмечает точную дату выборов, а пик появляется как раз в неделю выборов (покрыт светло-серой тенью).На рисунке 1 также показана средняя оценка влияния всех пользователей, которая имеет незначительные колебания. Пример демонстрирует, что влияние человека может меняться с течением времени и резко определяться конкретными событиями. Измерение изменяющегося во времени влияния важно для точного обнаружения действующих лиц, влияющих на ситуацию, что имеет решающее значение для таких приложений, как онлайн-маркетинг и политические кампании. РИСУНОК 1. - Изменение влияния, зависящее от времени. РИСУНОК 1. Чувствительное ко времени изменение влияния. Показать все Помимо времени, влияние пользователя сильно зависит от тематики [9] , [11] . Пользователи с высокими показателями глобального влияния могут не влиять на определенную тему и наоборот. Пример показан на рисунке 2 . Мы наносим на график оценки влияния двух пользователей Twitter по разным темам. Джефф Дин имеет более высокий общий балл влияния , чем Виталика Бутерин , 2 , особенно на темы AI , ML и больших данных . Тем не менее, Виталик Бутерин считается потенциальным влиятельным лицом в теме блокчейна . Анализ влияния по конкретной теме [9] имеет жизненно важное значение для многих приложений. ФИГУРА 2. Вариации влияния в зависимости от темы (AI, ML, CS относятся к темам « Искусственный интеллект» , « Машинное обучение» и « Информатика» соответственно). Показать все Огромное количество тем в социальных сетях активны и быстро развиваются, что требует единой структуры для совместного моделирования распространения влияния во времени и темах. В связи с вышеупомянутыми наблюдениями возникает вопрос: как можно измерить влияние, зависящее от времени и конкретной темы? Чтобы подойти к этой проблеме, необходимо решить три основных задачи. Во-первых, совместное моделирование распределения влияния по времени и темам включает комбинации двух типов характеристик, что непрактично для перечисления всех возможностей. Недавние работы [8] , [9] , [11] сосредоточены на использовании временных или тематических функций, но не обоих сразу. Во-вторых, социальные сети в реальной жизни состоят из нескольких типов взаимодействия с пользователем. Например, в Twitter [2], [12] , [13] , мы можем взаимодействовать с другими пользователями различными функциями , такие как наблюдения , ретвитые и упоминание и т.д. Ключевой вопрос заключается в том , чтобы оценить вклад различных взаимодействий , когда влияние распространяется. Существующие работы рассматривают только один тип взаимодействия или присваивают одинаковый вес разным типам взаимодействий [14] . В-третьих, узлов и ребер в социальных сетях бесчисленное множество, и они быстро развиваются [15] . Следовательно, контролируемые модели не могут в полной мере использовать крупномасштабные наборы данных, потому что только небольшая часть данных помечена достоверной информацией. Для решения проблем выше, мы предлагаем неконтролируемую модель, называемую Т IME-чувствительная и Т OPIC специфичный я nfluence М мерки ( TTIM модели). TTIM состоит из сети влияния и внимания и матрично-адаптивной долгосрочной краткосрочной памяти (LSTM) [16] , которую можно совместно обучить для автоматизации комбинаций функций в первом испытании. Предлагаемая сеть внимания влияния объединяет представления влияния узла с вниманием к различным типам взаимодействий [17] , [18]. Цель обучения без учителя может управлять системой обучения без надзора с земли. Предлагаемая нами структура также может быть естественным образом адаптирована для онлайн-обучения. Мы оцениваем предлагаемый метод с помощью пяти реальных наборов данных из Twitter и Reddit. Подводя итог, основные результаты этой работы: Насколько нам известно, мы первые, кто одновременно измеряет временное и тематическое влияние в социальных сетях. Мы предлагаем единую вычислительную структуру TTIM для решения задачи измерения социального влияния. Две подсети, сеть внимания и матрично-адаптивная LSTM, могут совместно изучать вклад различных взаимодействий и динамику влияния в социальных сетях. Фреймворк поддерживает как стандартное, так и онлайн-обучение. Мы используем пять наборов данных, полученных из Twitter и Reddit, для сравнения TTIM с современными моделями измерения социального влияния. Результаты экспериментов демонстрируют эффективность, действенность и масштабируемость предложенного метода. Остальная часть этой статьи организована следующим образом. В разделе II представлена ​​постановка задачи. Детали структуры показаны в Разделе III . В разделе IV представлены наборы данных и экспериментальные результаты, в которых наша модель сравнивается с современными методами. Раздел V резюмирует соответствующую работу, а Раздел VI завершает этот документ. РАЗДЕЛ II.Предварительные мероприятия В этом разделе мы определяем условные обозначения, используемые в статье, и формально определяем постановку задачи. A. Обозначения Обозначения в этой статье представлены в таблице 1 . ТАБЛИЦА 1 Термины и обозначения Table 1- Terms and Notations Б. Постановка проблемы Как было сказано в разделе I , мы стремимся измерить влияние в социальных сетях, зависящее от времени и конкретной темы. Предположим, что естьN пользователей, и каждый пользователь имеет два типа информации: текстовую и интерактивную. Например, в Twitter текстовая информация состоит из набора твитов, которые можно использовать для моделирования привязанности пользователей к определенным темам. Информация о взаимодействии может быть извлечена из действий между пользователями, таких как упоминание и ретвит в Twitter. Предположим, что у нас естьT временные интервалы и L Всего типов взаимодействий. Затем мы можем сформулировать социальные данные в виде последовательности временных графов с атрибутами, Определение 1 (графы с временными атрибутами): обозначаются как граммт= ( V ,Ат,Икст) , t = 1 , … , T , куда V это набор пользовательских узлов и | V | =N . Информация о взаимодействии формулируется как тензор смежностиАт∈рN× N× L для L типы взаимодействия в т -й временной интервал. Тензор сродства пользователя к темеИкст∈рN× M× D представляет текстовую информацию N пользователи в т -й интервал. M количество тем во всей социальной сети и D это измерение встраивания темы. Например, если л -й тип взаимодействия в Твиттере - упоминание иАт ( я дж л ) равно 2, то это означает, что пользователь я был дважды упомянут пользователем j в т -й интервал. Детализируем генерацию тензораИкст в Разделе III-A . Учитывая приведенное выше определение, мы вводим формулировку задачи: Проблема 1 (измерение влияния с учетом времени и конкретной темы): Учитывая временные атрибуты графов граммт= ( V ,Ат,Икст) , t = 1 , … , T которые представляют текстовую и интерактивную информацию в социальных сетях, цель состоит в том, чтобы вывести чувствительный ко времени и тематический тензор влияния B ∈рN× т× M для пользователей V . Необходимо ответить на несколько ключевых вопросов по проблеме 1 : 1) Как извлечь тензор сродства между пользователем и темой.Икст ? 2) Как мы оцениваем вклад различных типов взаимодействий во время распространения влияния? 3) Как мы объединяем текстовую и интерактивную информацию вместе? 4) Как мы измеряем влияние пользователей в зависимости от темы и времени в последовательности графиковграммт( t = 1 , … , T) неконтролируемым образом? РАЗДЕЛ III.Структура TTIM В этом разделе представлена ​​структура модели TTIM. Интуитивно понятная иллюстрация представлена ​​на рисунке 3 . В каждом временном интервале есть два типа необработанных данных: текстовые и интерактивные. Для текстовых данных мы используем Seded Latent Dirichlet Allocation (SeededLDA) [19], чтобы выполнить дистилляцию темы и получить тензор сродства между пользователем и темой в каждом временном интервале. Для временных графиковL типов взаимодействий, мы проектируем сеть влияния и внимания, чтобы моделировать процесс распространения влияния и изучать вклад различных взаимодействий. Затем временное влияние изучается путем оптимизации неконтролируемой целевой функции в матрично-адаптивной модели LSTM. Мы также разрабатываем онлайн-версию TTIM, немного изменяя конвейер. FIGURE 3. - The workflow of TTIM. In each time interval, we collect two types of data: streaming texts and multiple types of interactions. From raw text data, we distill topics and obtain a user-topic affinity tensor ${X}_{t}$ using the SeededLDA model. We combine multiple types of interactions with the influence attention network and obtain user representations ${F}_{t}$ . The matrix-adaptive LSTM learns the influence dynamics with the sequence of the influence features. After the model training with an objective function in the unsupervised fashion, we obtain time-sensitive and topic-specific influence scores of the users. РИСУНОК 3. Рабочий процесс ТТИМ. В каждом временном интервале мы собираем два типа данных: потоковые тексты и несколько типов взаимодействий. Из необработанных текстовых данных мы выделяем темы и получаем тензор сродства пользователя к теме.Икст используя модель SeededLDA. Мы комбинируем несколько типов взаимодействий с сетью влияния и внимания и получаем представления пользователей.Fт . Матрично-адаптивная LSTM изучает динамику влияния с последовательностью характеристик влияния. После обучения модели с целевой функцией в режиме неконтролируемого обучения мы получаем чувствительные ко времени и тематические оценки влияния пользователей. Показать все А. Тема дистилляции В социальных сетях у пользователя обычно есть интересы по нескольким темам. Тема дистилляции направлена ​​на изучениеD -мерный вектор Икст ( я J ) который представляет встраивание пользователя я по теме j вовремя т . Следовательно, мы объединяем сообщения, отправленные одним и тем же пользователем за один временной интервал, в один документ, в результате чегоN× т документы. Чтобы сфокусировать внимание пользователей на теме, мы используем модель SeededLDA [19] , которая может идентифицировать скрытые темы тремя способами: Неконтролируемый : Подобно обычному LDA [20] , распределение документов по темам извлекается из распределения вероятностей с априорным методом Дирихле. Контролируемый : SeededLDA принимает наборы семян слов в качестве представителя основных тем. Таким образом, мы можем получить распределение документов по темам в определенных областях. Онлайн : нежелательно переобучать тематическую модель с нуля всякий раз, когда появляются новые данные. Вместо этого с помощью онлайн-обучения мы могли бы постепенно обновлять модель, используя предыдущее распределение тематических слов в качестве исходных слов для передачи в SeededLDA. В сочетании с онлайн-моделью LSTM, представленной в разделе III-C , мы можем обучать модель постепенно по мере поступления новых данных. В каждом временном интервале мы перегоняем M темы и получить тензоры сродства пользователя к теме Икст∈рN× M× D, t = 1 , … , T . Для пользователяя , Икст ( я J : ) это термин частоты верхних D слова, относящиеся к теме j . Более крупный элемент в тензореИкст указывает на то, что пользователь уделяет больше внимания соответствующей теме. SeededLDA без учителя подходит для обучения TTIM с нуля, где он автоматически определяет темы в социальных сообщениях. Контролируемая и онлайн-мода адаптируется к онлайн-обучению модели TTIM. Б. Влияние на сеть внимания Мы строим сеть влияния и внимания, чтобы моделировать процесс распространения влияния и изучать вклад различных взаимодействий. Следуя формулировке раздела II-B , мы получаем тензор смежностиАт , t = 1 , … , T , соответствующий L типы взаимодействий. Интуитивно понятно, что разные типы взаимодействий играют разные роли в распространении влияния. В большинстве существующих работ рассматривается только один тип взаимодействия или придается вес взаимодействия [14] в соответствии со знанием предметной области. Вдохновленные Graph Attention Networks (GAT) [18] , [21] и DeepInf [10] , мы предлагаем сеть внимания влияния, которая может агрегировать распределение тематики узла с вниманием к особенностям и краям локального окружения узла в многотипных социальных сетях. сети. В частности, без потери общности, мы набросаем процесс влияния внимания на конкретного пользователя. я в моментальный снимок графика т . ПозволятьNя , т быть набором односкачковых соседей узла я вовремя т . В отличие от GAT или DeepInf, мы вводим коэффициенты внимания как для сходства пользователей с темами, так и для взаимодействий между пользователем и пользователем, ея , jзнак равноMLPϕ(Икст ( я ),Иксt ( j ),Ат ( я J : ))(1) Посмотреть источникRight-click on figure for MathML and additional features. куда j ∈Nя , т и коэффициент внимания ея , j измеряет относительное влияние этого пользователя я есть на пользователе j . MLPϕ это многослойная нейронная сеть с параметрами ϕ . Чтобы приспособить пользователей с разными размерами окрестностей, мы нормализуем коэффициенты с softmax, ая , jзнак равноexp(ея , j)∑k ∈Nя , тexp(ея , к)(2) Посмотреть источникRight-click on figure for MathML and additional features. В процессе распространения влияния сообщество социальной сети распространяет сообщения с несколькими раундами распространения. Поэтому мы предлагаем моделировать явления с несколькими уровнями влияния и внимания путем агрегирования векторов распределения тем узлов в их окрестностях. Тензор сродства пользователя к темеИкст используется в качестве входных узловых объектов для первого слоя (F( 0 )тзнак равноИкст ). Вп -й слой внимания влияния действует следующим образом: F( р )т ( я )= σ(∑j ∈Nя , тая , jF( п - 1 )t ( j )W( р ))(3) Посмотреть источникRight-click on figure for MathML and additional features. куда σ( ⋅ ) - нелинейная функция активации, такая как ReLU, F( р )т∈рN× M×d( р )п - представления выходного узла, а W( р )∈рd( п - 1 )п×d( р )п - матрица параметров для этого слоя. Тензор агрегированных признаковFт из выходных данных последнего слоя внимания влияния представляет распределение пользовательских тем после распространения влияния. C. Матрично-адаптивный LSTM С последовательностью агрегированных тензоров признаков Fт, t = 1 , … , T мы проектируем адаптивную к матрице сеть LSTM [22] , [23], чтобы узнать оценки влияния пользователей, зависящие от времени и тематические. Мы принимаем LSTM [24], мотивированные его значительной способностью к изучению долгосрочных зависимостей, которые естественным образом существуют во временных данных социальных сетей. Показанная в правой части рисунка 4 , матрично-адаптивная LSTM принимает последовательность матриц в качестве входных данных и выводит матрицы состояний всех временных точек, работая как рекуррентная модель «многие ко многим». FIGURE 4. - The aggregation of the user $i$ ’s textual and interactional information at the $t$ -th time interval and the information flow in an LSTM cell. The left part is the sample neighborhood of user $i$ at $t$ -th interval, which includes his/her 1-hop and 2-hop neighbors; the middle part illustrates the components of the aggregated feature $F_{t}$ which is the weighted sum of the affinity features of the neighborhood; the right figure shows the detailed structure of the LSTM cell introduced in Section III-C, with the aggregated features $F_{t}$ as its input data. РИСУНОК 4. Агрегация пользователя я текстовую и интерактивную информацию на т -й временной интервал и информационный поток в ячейке LSTM. Левая часть - образец окружения пользователя.я в т -й интервал, который включает его / ее соседей с 1 и 2 переходами; средняя часть иллюстрирует компоненты агрегированного признакаFт которая является взвешенной суммой аффинных характеристик окрестности; на правом рисунке показана подробная структура ячейки LSTM, представленная в разделе III-C , с агрегированными функциями.Fт в качестве входных данных. Показать все Уравнения из уравнения. 4 к уравнению. 8 описывают операции в матрично-адаптивной ячейке LSTM с размерностьюN опущено для простоты, ятзнак равнограммтзнак равноCтзнак равноОтзнак равноЧАСтзнак равноσ(FтWх я+ЧАСт - 1Wпривет я+Cт - 1Wс я+бя)σ(FтWx f+ЧАСт - 1Wh f+Cт - 1Wc f+бж)граммт⊙Cт - 1+ят⊙ танх(FтWx c+ЧАСт - 1Wh c+бc)σ(FтWх о+ЧАСт - 1Wх о+CтWc o+бо)От⊙ танх(Cт)(4)(5)(6)(7)(8) Посмотреть источникRight-click on figure for MathML and additional features. куда σ( ⋅ ) обозначает сигмовидную функцию σ( х ) = 1 / ( 1 +е- х) , а также ят,граммт∈ [ 0 , 1]M× P являются входом и воротами забыть. п - размер скрытых состояний модели LSTM. Cт∈рM× P - это состояние ячейки, являющееся ядром ячейки LSTM, обозначенное самой длинной вертикальной линией на рисунке 4 . Состояние клетки служит информационной связью между временем.т - 1 и время т . Ввод и ворота забвения, имеющие значения, нормализованные до [0, 1], помогают состоянию ячейки контролировать, сколько информации она должна принимать из входа (второй член в уравнении 6 ) и сколько унаследовано от предыдущего временного интервала (первый член в Уравнение 6 ).От∈ [ 0 , 1]M× P - выходной вентиль и ЧАСт∈рM× P состояние выхода. Выходной вентиль фильтрует информацию о состоянии ячейки.Cт и передает его в состояние выхода, которое служит выходом сети LSTM. В общем, сеть LSTM работает последовательно сFт в качестве начального ввода. Состояние клеткиCт вовремя т и состояние выхода ЧАСт будет многократно подаваться в ячейку LSTM за раз т + 1 . ВесWх ⋅∈рd( р )п× P , Wч ⋅∈рп× P , Wc ⋅∈рп× P и предубеждения бя,бж,бc,бо∈рп являются параметрами модели, которые обучаются методом обратного распространения с целевой функцией, введенной в Разделе III-D . Тензор влиянияB можно получить из конкатенации выходных состояний ЧАСт после объединяющего слоя. Возможные варианты для операции объединения включают максимальное, среднее и сумму. Матрично-адаптивная сеть LSTM может быть обобщена для поддержки онлайн-обучения. ВовремяТ′ , мы можем использовать модель, обученную во время Т′- 1 для вычисления расширенного тензора сродства пользователя к теме ИксТ′ и агрегированная матрица признаков FТ′ . Мы можем дополнительно обучить модель LSTM, начиная с параметров (W ) из предыдущей модели LSTM в момент времени Т′- 1 . Чтобы зафиксировать временную зависимость, мы устанавливаем окно временного интервалаТW в качестве гиперпараметра: только данные, поступившие во время [Т′-ТW,Т′] используется для переобучения модели LSTM. Это позволяет модели сойтись намного быстрее, чем переобучение с нуля. D. Целевая функция Чтобы измерить влияние, зависящее от времени и конкретной темы, мы учитываем три критерия при построении неконтролируемой целевой функции. Во-первых, пользователи с большим соседством и более высокой степенью близости должны иметь более высокий рейтинг влияния; Во-вторых, у активных пользователей больше шансов иметь высокий рейтинг влияния, чем у неактивных пользователей; Наконец, изменение матрицы влияния должно быть плавным. Основываясь на идеях, окончательная задача оптимизации строится в формуле. 9, чтобы изучить временную матрицу влияния пользователь-темаB ∈рN× т× M , макс L ( Вт,λл) =∑t = 1Т∑я = 1N∑j = 1NАт ( я J : )( 1 +∑k = 1NАт ( J K : )) ⋅∥B( Я т : )∥2+ζ1∑t = 1Т∑я = 1N∥Fт ( я )∥2⋅ ∥B( Я т : )∥2-ζ2∑t=2T∥B(:t:)−B(:t−1:)∥2F(9) Посмотреть источникRight-click on figure for MathML and additional features. куда At∈RN×N×L тензор смежности для L типы взаимодействия в t -й временной интервал; Ft агрегированный тензор сродства пользователя к теме во временном интервале t введена в Разделе III-B . Большее значениеB(itm) представляет пользователя i имеет большее влияние на тему m вовремя t . W содержит весовые матрицы в модели LSTM и влияет на сеть внимания. ζi> 0,i=1,2 являются компромиссными параметрами для уравновешивания трех компонентов. Добавляется ограничение для нормализации оценок влияния пользователя на тему для каждого временного интервала. Мы используем алгоритм обратного распространения во времени (BPTT) для обучения модели и изучения оценок влияния пользователя. С помощью предлагаемой нами сети влияния и внимания и матрично-адаптивного LSTM мы можем расширить модель TTIM на онлайн-моду. Изображаем псевдокод онлайн-обучения модели TTIM в алгоритме 1 . С течением времениT′ поступающих данных, модифицированная целевая функция =maxL(W,λl)∑t=T′−TWT′∑я =1N∑j = 1NАт ( я J )( 1+∑k = 1NАт ( j k )⋅∥B( Я т : )∥2)+ζ1∑т=Т′−ТWТ′∑я = 1N∥Fт ( я )∥2⋅ ∥B( Я т : )∥2-ζ2∑т=Т′-ТW+ 1Т′∥B( : Т : )-B( : Т - 1 : )∥2F(10) Посмотреть источникRight-click on figure for MathML and additional features. Алгоритм 1 TTIM-Online с своевременным поступлением новых данных T′ A(l)t , Ft , куда t=T′−TW,…,T′ , документы dT′ , предыдущий SeededLDA (Т′- 1 ), предыдущий LSTM (Т′- 1 ), эпоха обучения пэпоха , гиперпараметры α,ζ1,ζ2,ТW Загрузите распределение тематических слов из SeededLDA (Т′- 1 ) в качестве раздачи семян для SeededLDA (Т′ ) Поезд SeededLDA (Т′ ) с участием dТ′ . Вычислить ИксТ′( я j ) Вычислить FТ′ используя уравнение. 1 , 2 , 3 Нагрузка W из LSTM (Т′- 1 ) в LSTM (Т′ ) для e p o c h = 1 ; e p o c h≤пэпоха делать для t =Т′-ТW; t ≤Т′ делать Вычислить ят,граммт,Cт,От,ЧАСт используя уравнение. 4 – Ур. 8 конец для Вычислить L(W,λl) используя уравнение. 10 Обратное распространение и обновление W конец для Таким образом, наша модель TTIM отвечает на вопросы, поднятые в Разделе II-B, с помощью хорошо разработанного конвейера: модель SeededLDA изучает тензор сродства между пользователем и темой; тензоры смежности для различных взаимодействий интегрированы с обучаемыми весами; сеть влияния и внимания имитирует распространение влияния; матрично-адаптивная модель LSTM фиксирует долгосрочные зависимости и изучает оценки влияния после решения задачи оптимизации. Потоковые тексты и динамические социальные сети моделируются совместно для измерения социального влияния. РАЗДЕЛ IV.Эксперименты В этом разделе мы оцениваем предлагаемый нами метод с помощью обширных экспериментов. Во-первых, мы вводим помеченные наборы данных для количественной оценки нашей модели с помощью задачи обнаружения влиятельных лиц, показанной в Разделе IV-A . Во-вторых, мы качественно оцениваем чувствительные ко времени и тематические свойства модели TTIM с большими немаркированными наборами данных в Разделе IV-B . В-третьих, в Разделе IV-C показано, что предложенный метод TTIM-Online эффективен при обучении и позволяет достичь соревновательных результатов . Наконец, мы проводим анализ чувствительности к параметрам и масштабируемости в Разделе IV-D . А. Эксперименты с помеченными наборами данных В этом разделе мы подробно описываем экспериментальные результаты по задаче обнаружения влиятельных лиц с тремя помеченными наборами данных. Задача направлена ​​на выявление самых влиятельных людей из всех пользователей социальных сетей. Сначала мы представляем наборы данных и базовые показатели, а затем результаты обнаружения влиятельных лиц. 1) Наборы данных Мы создали три вручную меченых наборы данных из Twitter ( Политика набора и технологии набора ) и Reddit ( Reddit набора ). Статистика набора данных представлена ​​в таблице 2 . Более подробную информацию о предварительной обработке можно найти в дополнительных материалах. ТАБЛИЦА 2 Статистика наборов данных Таблица 2 - Статистика наборов данных В двух наборах данных из Twitter мы пометили влиятельных лиц, выбрав пользователей с большой группой подписчиков, активное участие в политических / технологических темах и главное глобальное влияние на действия других пользователей. Этикетки были отобраны большинством голосов трех человек-этикетировщиков. Набор « Политика» содержит 1031 пользователя, которые отправляют твиты на политическую тему, и 64 из них помечены как влиятельные лица. Есть 10 недельных интервалов и всего 1 840 552 твита. Набор « Технологии» содержит 1122 пользователя, которые отправляют твиты, связанные с технологиями, и 80 из них отмечены как влиятельные лица. Всего имеется 7 однодневных интервалов и 141 835 твитов. Reddit - это онлайн-дискуссионный форум, где пользователи публикуют и комментируют контент в различных тематических сообществах. На платформе Reddit пользователи могут голосовать за сообщения, которые они поддерживают, поэтому количество голосов может указывать на влияние сообщений и их отправителей. Мы пометили пользователей, чьи сообщения получили наибольшее количество голосов, как лидеров мнений. Набор Reddit взят из дампа комментариев Reddit 3 мая 2015 года и содержит 35 267 пользователей, из которых 100 помечены как влиятельные лица. Мы строим граф взаимодействия пользователя с пользователем, связывая пользователей, если один пользователь комментирует сообщение другого пользователя. В наборе Reddit 31 однодневный интервал и 126 125 сообщений / комментариев . 2) Исходные данные Мы сравниваем предложенную модель TTIM со следующими семью репрезентативными исходными условиями: Последователи . Функция, используемая в этом базовом показателе, - это количество подписчиков пользователя. Обратите внимание, что у нас есть доступ к этой функции только в Twitter, но не на Reddit. TwitterRank [11] - это расширение алгоритма PageRank, который использует LDA для поиска некоторых тем, а затем вычисляет рейтинг пользователей по темам на основе их влияния на подписчиков и их интересов в этих темах. Актуальное распространение аффинности (TAP) [25] - это модель распространения актуальной аффинности, построенная на факторном графе для определения социального влияния конкретной темы. ReFluence [26] - это статистическая и аналитическая модель, основанная на топологии влияния Эдельмана для определения роли и влияния пользователей друг на друга. Здесь мы рассматриваем «стартер идеи» и «усилитель», определенные в этой базовой линии, как влиятельные лица, а остальных - как обычных пользователей. Модель RR-LT [8] использует функцию весов ребер и собственный вес узлов для представления вероятностей влияния в рамках модели линейного порога. Для аппроксимации влияния узлов используются методы на основе опроса и выборка случайных наборов с обратной достижимостью. Модель RR-IC [8] использует вероятность распространения, опрос и случайные наборы обратной достижимости для отслеживания влиятельных лиц в рамках модели независимого каскада. CoupledGNN [27] применяет две нейронные сети со связанными графами для итеративного моделирования и прогнозирования популярности с учетом сети. 3) Экспериментальные настройки Предлагаемый TTIM реализован в среде Tensorflow [28] . Оптимизатором обучения является Адам [29] со скоростью обучения 0,0005,β1=0.9 , а также β2=0.999 . Эксперименты проводятся на сервере Linux с GPU Tesla V100 объемом 16 Гбайт, 20 процессорами Intel Xeon E5-2698 и памятью 512 Гбайт. Мы используем поиск по сетке для настройки гиперпараметров. Измерение встраивания темыD выбирается из {5, 10, 20, 30}. Компромиссные параметры в уравнении 9 (ζ1,ζ2 ) ищутся от 10 −4 до 10 4 с шагом 10 1 . Мы инициализируем весовые матрицы в предлагаемой модели TTIM с инициализацией Xavier [30] . Чтобы определить влиятельных лиц в помеченных наборах данных, мы суммируем изученную оценку влияния всех тем и максимальный пул с течением времени, чтобы получить оценку влияния каждого пользователя. Прогнозы на выходе будут самыми лучшими.k пользователи с наивысшими оценками влияния. Мы оцениваем эффективность обнаружения Influencer по точности , F1-измерения , 4 и АУК метрик [31] . Все результаты представляют собой среднее значение 10 повторных запусков. 4) Экспериментальные результаты В Таблице 3 приведены подробные результаты обнаружения верхнихk влиятельные лица, где k количество положительных образцов в основной истине (k=64 для набора "Политика" ,k=80 для набора технологий иk=100 для набора Reddit ). 5 Лучшие результаты выделены жирным шрифтом. Результаты показывают, что TTIM эффективен и превосходит другие базовые показатели по точности, F1 и AUC для этих наборов данных. Рисунок 5 дополнительно иллюстрирует точность приk , куда k - количество лидеров мнений, определенных каждым методом. Мы можем заметить, что TTIM всегда поддерживает более высокий уровень точности, чем базовые, и имеет 100% точность по сравнению с топ-20 наборами «Политика» и «Технологии». Эти наблюдения подтверждают выдающуюся способность TTIM обнаруживать лидеров мнений. Мы объясняем это существенное улучшение следующими двумя причинами. Во-первых, TTIM рассматривает различные источники, включая текстовое содержание и множественные взаимодействия. По сравнению с базовыми уровнями, такими как CoupledGNN, которые одинаково обрабатывали взаимодействия, TTIM автоматически изучает различные веса взаимодействий с помощью механизма внимания. Во-вторых, TTIM хорошо моделирует временные данные с помощью LSTM, чтобы узнать оценку влияния с помощью потокового текста и динамических социальных сетей, интегрированных без проблем. ТАБЛИЦА 3 Экспериментальные результаты с помеченными наборами данных Таблица 3 - Результаты экспериментов с помеченными наборами данных РИСУНОК 5. - Точность обнаружения топ-$ k $ влиятельных лиц в помеченных наборах данных. РИСУНОК 5. Точность высочайшегоk обнаружение влиятельных лиц в помеченных наборах данных. Показать все Мы проводим исследование абляции, поочередно удаляя механизм внимания (TTIM с вниманием) и LSTM (TTIM с LSTM). Как показывают результаты в таблице 3 , каждый модуль способствует повышению производительности, а предлагаемый TTIM извлекает выгоду из процесса распространения влияния, усвоенного сетью влияния и внимания, и чувствительного ко времени шаблона, усвоенного матрично-адаптивным LSTM. Мы также подчеркиваем способность TTIM извлекать зависящие от времени и тематические оценки влияния пользователей с помеченными наборами данных Twitter, показанными на Рисунке 6 (a), (c) для набора Политика и на Рисунке 6 (b), ( г) для Технологического набора . Мы можем наблюдать некоторые интересные явления. Например, на рис. 6 (a) показан не только пик для пользователя Twitter Дугласа Джонса, но и аналогичная тенденция для пользователей TheDailyEdge и TeaPainUSA . Вероятной причиной этого может быть то, что они принадлежат к той же политической партии, что и Дуглас Джонс, и получают влиятельные выгоды от избирательного события. Еще одна находка - этот пользовательОценка влияния Виталика Бутерина в основном ограничена тематическим блокчейном . Это могло быть причиной того, что тенденция его влияния схожа с ценой биткойнов в тот период. РИСУНОК 6. - Чувствительное ко времени влияние (a, b) и тематическое влияние (c, d) для наиболее влиятельных лиц в наборах данных о политике и технологиях. РИСУНОК 6. Чувствительное ко времени влияние (a, b) и влияние конкретной темы (c, d) для наиболее влиятельных лиц в наборах данных о политике и технологиях . Показать все Б. Эксперименты с немаркированными наборами данных В этом разделе мы обсуждаем экспериментальные результаты по измерению влияния на большие немаркированные наборы данных. 1) Наборы данных Мы используем два немаркированных набора данных. Набор LV-стрельба содержит 1% всех твитов за период с 1 октября 2017 года по 11 октября 2017 года. Ночью 1 октября 2017 года боевика произвела более 1100 выстрелов по толпе посетителей концертов на шоссе 91. Музыкальный фестиваль Harvest в Лас-Вегасе, в результате чего 58 человек погибли и 851 получили ранения. 6 Это событие вызвало огромный резонанс в социальных сетях, поэтому мы сканировали твиты в течение следующих 11 дней. После предварительной обработки данных набор данных содержал 2 859 809 пользователей, 17 635 937 твитов и 11 однодневных интервалов. Другой общий набор данных содержит 1% твитов за три года (август 2016 г. - июль 2019 г.). Набор данных содержал 1 893 174 пользователя и 15 953 165 твитов с 36 временными интервалами в один месяц. 2) Результаты В таблице 4 показаны 5 самых популярных тем с их ключевыми словами и наиболее влиятельными лицами. Мы называем эти темы, чтобы упростить изложение. Интуитивно понятно, что лидеры мнений очень актуальны для соответствующих тем. Например, можно было бы ожидать, что Дональд Трамп , Майк Пенс и Хиллари Клинтон будут влиять на темы, связанные с политикой , точно так же, как можно было бы ожидать, что такие общественные деятели, как Рианна (певица) и Джейк Таппер (журналист), а также обмен видео в Интернете платформа ( Youtube ), чтобы иметь влияние в молитвенной деятельности после трагедии со стрельбой в Лас-Вегасе. ТАБЛИЦА 4 Выборка топ-5 тем и их влиятельных лиц в LV-Shooting и общих наборах данных Таблица 4 - Выборка топ-5 тем и их влиятельных лиц в LV-Shooting и общих наборах данных Мы исследуем зависящее от времени и тематическое свойство оценки влияния соответственно на рисунках 7 (a), (b) и 7 (c), (d) . Мы показываем оценки влияния пяти ведущих влиятельных лиц, обнаруженных TTIM в этих двух наборах данных. На рисунке 7 (а) пик влияния пришелся на 1 октября 2017 г., сразу после стрельбы в Лас-Вегасе , у четырех пользователей , за исключением BleacherReport (спортивная платформа). Из рисунка 7 (b) видно, что Дональд Трамп и две новостные платформы Fox News и The New York Timesимеют очевидные пики в период президентских выборов (с октября по ноябрь 2016 г.) и инаугурации президента (с декабря 2016 г. по январь 2017 г.), что вполне разумно. Мы можем видеть, что учетная запись Дональда Трампа имеет относительно высокое влияние за этот период в обоих наборах данных из-за его активности в Твиттере. На рисунке 8 показаны трехмерные графики оценки влияния Дональда Трампа в наборах данных LV-Shoot и General соответственно. Мы видим, что оценка влияния значительно варьируется в зависимости от времени и темы. Таким образом, предлагаемая нами модель TTIM отражает влияние, зависящее от времени и конкретной темы, в крупном масштабе и может идентифицировать влиятельных лиц с различной степенью детализации по времени. FIGURE 7. - Time-sensitive influence (a, b) and topic-specific influence (c, d) for the top influencers in LV-shooting and General datasets. РИСУНОК 7. Чувствительное ко времени влияние (a, b) и тематическое влияние (c, d) для основных влиятельных лиц в наборах данных LV-Shoot и General . Показать все РИСУНОК 8. - Вариация оценки влияния Дональда Трампа в (а) наборе для стрельбы LV; и (b) Общий набор. РИСУНОК 8. Вариация оценки влияния Дональда Трампа в (а) съемочной площадке LV; и (b) Общий набор. Показать все C. Онлайн-обучение Предлагаем сравнение стандартной модели TTIM и TTIM-Online. Когда новые данные поступают вовремяT′ : TTIM переобучается со всеми данными, поступившими на данный момент, т. Е. За время[1,T′] TTIM-Online стартует из предыдущей модели, обученной на данных[1,T′−1] , и обновляет модель только с использованием последних данных, как описано в алгоритме 1 . Оба алгоритма работают до тех пор, пока модели не сойдутся. Окно временного интервалаTW в модели LSTM в TTIM-Online установлено значение 3. Мы показываем производительность TTIM-Online в Таблице 3 и на Рисунке 5 . TTIM-Online по-прежнему превосходит базовые модели по точности, F1 и AUC на помеченных наборах данных. На рисунке 9 показаны подробные сведения о точности и времени обучения TTIM и TTIM-Online в наборах « Политика» и « Технологии» . На рисунке 9 (а) мы видим, что оба алгоритма достигают одинаковой точности при обнаружении факторов влияния. Вначале поступление новых данных повысит точность, пока модель не достигнет насыщения и ее производительность не выйдет на плато. Однако рисунок 9 (б)показывает, что онлайн-версия модели TTIM намного более эффективна и масштабируема, чем стандартная модель TTIM. Время обучения онлайн-модели TTIM остается на постоянном уровне для каждой временной метки, тогда как время обучения, занимаемое стандартной моделью TTIM на каждой временной метке, линейно растет с увеличением количества временных меток. РИСУНОК 9. - Сравнение TTIM и TTIM-Online. РИСУНОК 9. Сравнение TTIM и TTIM-Online. Показать все D. Исследование параметров и масштабируемость В этом разделе мы визуализируем коэффициенты внимания, относящиеся к различным взаимодействиям в уравнении 1 . Средние значения для четырех наборов данных Twitter показаны в таблице 5 . Мы видим, что у взаимодействия с цитатой самые большие коэффициенты во всех наборах данных. Это свидетельствует о том, что люди более глубоко под влиянием других людей , когда они решают цитировать твиты и записывать чувства, хештеговимеют относительно меньшие коэффициенты, вероятно, потому, что один хэштег обычно упоминается многими пользователями, и трудно отследить источник влияния. Кроме того, у хэштега есть несколько синонимов, что может еще больше усложнить распространение влияния. Что касается чувствительности параметра, мы строим AUC при поиске по сетке дляζ пары, показанные на рисунке 10 . Модель отдает предпочтение меньшемуζ2 и оптимизированный ζ1 значение для достижения максимальной производительности. ТАБЛИЦА 5 Визуализация параметров коэффициентов по пяти взаимодействиям Table 5- Visualization on Coefficients Parameters With Respect to the Five Interactions FIGURE 10. - AUC of Politics set with different parameter $\zeta $ pairs. РИСУНОК 10. Набор AUC политики с другим параметромζ пары. Показать все FIGURE 11. - (a) Training time with respect to data size; (b) Convergence curves on two large datasets. РИСУНОК 11. а) время обучения с учетом размера данных; (б) Кривые сходимости на двух больших наборах данных. Показать все Мы оцениваем масштабируемость TTIM, измеряя время обучения как функцию количества пользователей и скорости сходимости для двух больших немаркированных наборов данных на рисунке 11 . На рисунке 11 (а) показано время обучения TTIM, соответствующее разному количеству пользователей (N ). Мы видим, что время обучения увеличивается примерно линейно по мере роста числа пользователей, что подтверждает, что TTIM хорошо масштабируется для больших наборов данных. На рисунке 11 (b) показаны кривые сходимости для двух больших наборов данных, демонстрирующие, что TTIM быстро сходится на обоих наборах данных. РАЗДЕЛ V.Связанных с работой Проблема измерения влияния направлена ​​на количественную оценку влияния пользователей в социальных сетях и выявление влиятельных лиц. Большинство предыдущих моделей были сосредоточены на формулировании пользовательских взаимодействий в графах и обнаружении влиятельных узлов на основе сформулированного графа с помощью PageRank [11] , поиска по темам, вызванного гиперссылками (HITS) [32] , вероятностного случайного блуждания по графам опыта [33] или их варианты [34] . Deepinf [10] и NNMLinf [35] пытались смоделировать социальное влияние на микроуровне и спрогнозировать действия пользователя после воздействия местного окружения. Метод на основе нейронных сетей с двумя связанными графами, CoupledGNN [27], был предложен для прогнозирования популярности в социальных сетях путем улавливания эффекта каскадирования при распространении информации. По сравнению с Deepinf и NNMLinf, предлагаемый нами TTIM направлен на измерение влияния на макроуровне и моделирование его динамики, что имеет жизненно важное значение для глобальной идентификации влиятельных лиц. По сравнению с Coupled-GNNs и их аналогами, наш метод TTIM рассматривает конкретные темы во время исследования влияния, а не только каскадные эффекты (т.е. эффекты, чувствительные ко времени). Помимо ванильной проблемы, если мы проигнорируем влияние времени на измерение, выявление факторов влияния на конкретную тему изучалось в нескольких предыдущих работах [25] , [36] - [37] [38] . TwitterRank [11] использовал как структуру сети, так и схожесть тем при расчете влияния пользователей на Twitter. Bi et al. [9] предложил метод Бернулли-полиномиального смешения, который совместно моделировал текст и подписку. И если мы игнорируем влияние конкретных тем на измерение, анализ динамики влияния привлекает множество интересов, учитывая развивающуюся природу социальных сетей [39] , [40]. Aggarwal et al. [41] предложили обнаружение влиятельных узлов в динамических сетях с использованием подхода прямой и обратной трассировки. Ян и др. [8] изучали отслеживание влиятельных узлов и максимизацию влияния [42] , [43] путем моделирования динамических изменений в виде потока обновлений веса ребер. Таким образом, не существует работ по измерению чувствительного ко времени и тематическому влиянию в социальных сетях. Это побуждает нас предложить LSTM и TTIM, основанный на самовнимании, который объединяет потоковые тексты и мультиплексные взаимодействия для измерения временного социального влияния на различные темы. РАЗДЕЛ VI.Заключение В данной статье исследуется проблема измерения влияния времени и тематики в социальных сетях. Вычислительная структура, чувствительное ко времени и измерение влияния конкретной темы, предложена на основе сети внимания влияния и матрично-адаптивного LSTM. Благодаря множеству типов взаимодействий и потоковой передачи текстов сеть влияния внимания имитирует распространение влияния самовниманием. LSTM с адаптацией к матрице фиксирует долгосрочные зависимости и изучает оценки влияния после решения задачи оптимизации. Всесторонняя оценка предлагаемого метода проводится с использованием пяти наборов данных из Twitter и Reddit. Результаты экспериментов показывают превосходную эффективность TTIM по сравнению с современными моделями анализа социального влияния. Применяя предложенную модель TTIM к крупномасштабным данным Twitter, ПОДТВЕРЖДЕНИЕ Работа частично поддержана Национальным институтом здоровья (U01HG008488), Национальным институтом аллергии и инфекционных заболеваний (R56AI125105 и 7R01AI132030) и Национальным институтом психического здоровья (5R01MH106415). Авторы благодарят анонимных рецензентов за внимательное чтение и содержательные комментарии к нашей рукописи. Авторы Цифры использованная литература Цитаты Ключевые слова Ключевые слова IEEE Тензоры , Твиттер , Голосование , Модели данных , Обучение , Модели адаптации INSPEC: контролируемое индексирование визуализация данных , политика , повторяющиеся нейронные сети , социальные сети (онлайн) , анализ текста INSPEC: неконтролируемое индексирование потоковые тексты , динамические социальные сети , влияние на процесс распространения , динамика влияния , Модель TTIM , распределение тем , политическое влияние , Влияние Дугласа Джонса , статические структуры социальных сетей , популярные социальные сети , измерение влияния по конкретной теме , Модель TTIM , матрично-адаптивная долговременная кратковременная память , Твиттер , Reddit Ключевые слова автора Влияние общества , чувствительный ко времени , тематический , LSTM , самовнимание Метрики СМИ Сноски Больше похоже на это На пути к набору данных золотого стандарта для извлечения открытой информации на итальянском языке 2019 Шестая международная конференция по анализу, управлению и безопасности социальных сетей (SNAMS) Опубликовано: 2019 Интернет-СМИ как монитор цен: анализ текста с использованием метода извлечения текста и алгоритма сходства Яро-Винклера 2020 Новые технологии в вычислениях, связи и электронике (ETCCE) Опубликовано: 2020 Показать больше использованная литература 1. ХК Кельман, «Идентификация соответствия и интернализация трех процессов изменения отношения», J. Conflict Resolution , vol. 2, стр. 51-60, март 1958 г. Показать в контексте CrossRef Google ученый 2. AS Badashian и E. Stroulia, "Измерение влияния пользователей в GitHub: ошибка миллиона подписчиков", Proc. 3-й Int. Мастерская CrowdSourcing Softw. Англ. CSI-SE , стр. 15-21, май 2016 г. Показать в контексте Google Scholar 3. Ф. Рикельме и П. Гонсалес-Кантергиани, «Измерение влияния пользователей на Twitter: обзор», Inf. Процесс. Управлять. , т. 52, нет. 5, pp. 949-975, сентябрь 2016 г. Показать в контексте CrossRef Google ученый 4. М. Ричардсон и П. Домингос, "Майнинг сайтов обмена знаниями для вирусного маркетинга", Proc. 8-й ACM SIGKDD Int. Конф. Знай. Discovery Data Mining KDD , стр. 61-70, 2002. Показать в контексте Google Scholar 5. П. Домингос и М. Ричардсон, "Анализ сетевой ценности клиентов", Proc. 7-й ACM SIGKDD Int. Конф. Знай. Discovery Data Mining KDD , стр. 57-66, 2001. Показать в контексте Google Scholar 6. С. Ранганатх, X. Ху, Дж. Тан и Х. Лю, «Понимание и определение сторонников политических кампаний в социальных сетях», Proc. 9-й ACM Int. Конф. WSDM , интеллектуальный анализ данных веб-поиска , стр. 43-52, 2016. Показать в контексте Google Scholar 7.J. Tang, S. Wu and J. Sun, "Confluence: Conformity influence in large social networks", Proc. 19th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining KDD, pp. 347-355, 2013. Show in Context Google Scholar 8.Y. Yang, Z. Wang, J. Pei and E. Chen, "Tracking influential individuals in dynamic networks", IEEE Trans. Knowl. Data Eng., vol. 29, no. 11, pp. 2615-2628, Nov. 2017. Show in Context View Article Full Text: PDF (1388KB) Google Scholar 9.B. Bi, Y. Tian, Y. Sismanis, A. Balmin and J. Cho, "Scalable topic-specific influence analysis on microblogs", Proc. 7th ACM Int. Conf. Web Search Data Mining WSDM, pp. 513-522, 2014. Show in Context Google Scholar 10.J. Qiu, J. Tang, H. Ma, Y. Dong, K. Wang and J. Tang, "Deepinf: Social influence prediction with deep learning", Proc. KDD, pp. 2110-2119, 2018. Show in Context Google Scholar 11.J. Weng, E.-P. Lim, J. Jiang and Q. He, "Twitterrank: Finding topic-sensitive influential twitterers", Proc. WSDM, pp. 261-270, 2010. Show in Context Google Scholar 12.E. Bakshy, J. M. Hofman, W. A. Mason and D. J. Watts, "Everyone’s an influencer: Quantifying influence on twitter", Proc. WSDM, pp. 65-74, 2011. Show in Context Google Scholar 13.S. Wu, J. M. Hofman, W. A. Mason and D. J. Watts, "Who says what to whom on Twitter", Proc. 20th Int. Conf. World Wide Web WWW, pp. 705-714, 2011. Show in Context Google Scholar 14.K. Garimella, I. Weber and M. De Choudhury, "Quote RTs on Twitter: Usage of the new feature for political discourse", Proc. 8th ACM Conf. Web Sci. WebSci, pp. 200-204, 2016. Show in Context Google Scholar 15.J. Leskovec, J. Kleinberg and C. Faloutsos, "Graphs over time: Densification laws shrinking diameters and possible explanations", Proc. 11th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining KDD, pp. 177-187, 2005. Show in Context Google Scholar 16.S. Hochreiter and J. Schmidhuber, "Long short-term memory", Neural Comput., vol. 9, no. 8, pp. 1735-1780, 1997. Show in Context View Article Full Text: PDF (237KB) Google Scholar 17.A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, et al., "Attention is all you need", Proc. NIPS, pp. 5998-6008, 2017. Show in Context Google Scholar 18.P. VeličkoviÄć, G. Cucurull, A. Casanova, A. Romero, P. Liò and Y. Bengio, "Graph attention networks", Proc. ICLR, pp. 1-12, 2018. Show in Context Google Scholar 19.J. Jagarlamudi, H. Daumé and R. Udupa, "Incorporating lexical priors into topic models", Proc. EACL, pp. 204-213, 2012. Show in Context Google Scholar 20.D. M. Blei, A. Y. Ng and M. I. Jordan, "Latent Dirichlet allocation", J. Mach. Learn. Res., vol. 3, pp. 993-1022, Jan. 2003. Show in Context Google Scholar 21.J. Zhang, X. Shi, J. Xie, H. Ma, I. King and D.-Y. Yeung, "GaAN: Gated attention networks for learning on large and spatiotemporal graphs", arXiv:1803.07294, 2018, [online] Available: http : // arxiv . org / abs / 1803 . 07294 . Show in Context Google Scholar 22.F. A. Gers and J. Schmidhuber, "Recurrent nets that time and count", Proc. IEEE-INNS-ENNS Int. Joint Conf. Neural Networks. IJCNN. Neural Comput. New Challenges Perspect. New Millennium, pp. 189-194, Jul. 2000. Show in Context View Article Full Text: PDF (512KB) Google Scholar 23.W. Yu, C. Zheng, W. Cheng, C. C. Aggarwal, D. Song, B. Zong, et al., "Learning deep network representations with adversarially regularized autoencoders", Proc. 24th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, pp. 2663-2671, Jul. 2018. Show in Context Google Scholar 24.A. Graves, "Generating sequences with recurrent neural networks", arXiv:1308.0850, 2013, [online] Available: https : // arxiv . org / abs / 1308 . 0850 . Show in Context Google Scholar 25.J. Tang, J. Sun, C. Wang and Z. Yang, "Social influence analysis in large-scale networks", Proc. 15th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining - KDD, pp. 807-816, 2009. Show in Context Google Scholar 26.R. Tinati, L. Carr, W. Hall and J. Bentwood, "Identifying communicator roles in Twitter", Proc. 21st Int. Conf. Companion World Wide Web WWW Companion, pp. 1161-1168, 2012. Show in Context Google Scholar 27.Q. Cao, H. Shen, J. Gao, B. Wei and X. Cheng, "Popularity prediction on social platforms with coupled graph neural networks", Proc. 13th Int. Conf. Web Search Data Mining, pp. 70-78, Jan. 2020. Show in Context Google Scholar 28.M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, et al., "Tensorflow: A system for large-scale machine learning", Proc. OSDI, pp. 265-283, 2016. Show in Context Google Scholar 29.D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization", Proc. ICLR, pp. 1-15, 2015. Show in Context Google Scholar 30.X. Glorot and Y. Bengio, "Understanding the difficulty of training deep feedforward neural networks", Proc. AISTATS, pp. 249-256, Mar. 2010. Show in Context Google Scholar 31.J. Huang and C. X. Ling, "Using AUC and accuracy in evaluating learning algorithms", IEEE Trans. Knowl. Data Eng., vol. 17, no. 3, pp. 299-310, Mar. 2005. Show in Context View Article Full Text: PDF (1216KB) Google Scholar 32.C. S. Campbell, P. P. Maglio, A. Cozzi and B. Dom, "Expertise identification using email communications", Proc. 12th Int. Conf. Inf. Knowl. Manage. CIKM, pp. 528-531, 2003. Show in Context Google Scholar 33.P. Serdyukov, H. Rode and D. Hiemstra, "Modeling multi-step relevance propagation for expert finding", Proc. 17th ACM Conf. Inf. Knowl. Mining CIKM, pp. 1133-1142, 2008. Show in Context Google Scholar 34.B. Gao, T.-Y. Liu, W. Wei, T. Wang and H. Li, "Semi-supervised ranking on very large graphs with rich metadata", Proc. 17th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining KDD, pp. 96-104, 2011. Show in Context Google Scholar 35.X. Wang, Z. Guo, X. Wang, S. Liu, W. Jing and Y. Liu, "NNMLInf: Social influence prediction with neural network multi-label classification", Proc. ACM Turing Celebration Conf. China ACM TURC, pp. 1-5, 2019. Show in Context Google Scholar 36.S. Chen, J. Fan, G. Li, J. Feng, K.-L. Tan and J. Tang, "Online topic-aware influence maximization", Proc. VLDB Endowment, vol. 8, no. 6, pp. 666-677, Feb. 2015. Show in Context CrossRef Google Scholar 37.A. Pal and S. Counts, "Identifying topical authorities in microblogs", Proc. 4th ACM Int. Conf. Web Search Data Mining WSDM, pp. 45-54, 2011. Show in Context Google Scholar 38.J.-V. Cossu, N. Dugue and V. Labatut, "Detecting real-world influence through Twitter", Proc. 2nd Eur. Netw. Intell. Conf., pp. 83-90, Sep. 2015. Show in Context View Article Full Text: PDF (252KB) Google Scholar 39.M. Sha, Y. Li, Y. Wang, W. Guo and K.-L. Tan, "River: A real-time influence monitoring system on social media streams", Proc. IEEE Int. Conf. Data Mining Workshops (ICDMW), pp. 1429-1434, Nov. 2018. Show in Context View Article Full Text: PDF (1737KB) Google Scholar 40.H. Zhuang, Y. Sun, J. Tang, J. Zhang and X. Sun, "Influence maximization in dynamic social networks", Proc. IEEE 13th Int. Conf. Data Mining, pp. 1313-1318, Dec. 2013. Show in Context View Article Full Text: PDF (250KB) Google Scholar 41.C. C. Aggarwal, S. Lin and P. S. Yu, "On influential node discovery in dynamic social networks", Proc. SIAM Int. Conf. Data Mining, pp. 636-647, Apr. 2012. Show in Context CrossRef Google Scholar 42.D. Kempe, J. Kleinberg and É. Tardos, "Maximizing the spread of influence through a social network", Proc. 9th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining KDD, pp. 137-146, 2003. Show in Context Google Scholar 43. W. Chen, Y. Wang и S. Yang, "Максимизация эффективного влияния в социальных сетях", Proc. KDD , стр. 199-208, 2009. Показать в контексте Google Scholar Личный кабинет IEEE ИЗМЕНИТЬ ИМЯ ПОЛЬЗОВАТЕЛЯ / ПАРОЛЬ Детали покупки ВАРИАНТЫ ОПЛАТЫ ПРОСМОТР ПРИОБРЕТЕННЫХ ДОКУМЕНТОВ информация профиля НАСТРОЙКИ СВЯЗИ ПРОФЕССИЯ И ОБРАЗОВАНИЕ ТЕХНИЧЕСКИЕ ИНТЕРЕСЫ Нужна помощь? США И КАНАДА: +1800678 4333 ПО ВСЕМУ МИРУ: +1732 981 0060 КОНТАКТНАЯ ПОДДЕРЖКА Следовать О IEEE Xplore | Свяжитесь с нами | Помощь | Доступность | Условия использования | Политика недискриминации | Отчетность по этике IEEE| Карта сайта | Конфиденциальность и отказ от файлов cookie IEEE - некоммерческая организация, крупнейшая в мире профессиональная техническая организация, занимающаяся продвижением технологий на благо человечества. © Copyright 2021 IEEE - Все права защищены. Использование этого веб-сайта означает ваше согласие с условиями. PDF Помощь

[5]. Текст взят из Википедии.