An Algorithm for Constructing Associative Series of Hashtags for Semantic Navigation in Social Networks

Full Text

1. Введение Хештеги являются важным механизмом семантической навигации в социальных сетях. В данной работе в качестве примера мы используем Инстаграм2, однако обычно другие современные социальные сети обладают похожим функционалом. В рассматриваемой социальной сети хештеги одновременно выполняют функции входящих и исходящих ссылок. В первую очередь хештег используется как исходящая ссылка от публикации к автоматически сгенерированной странице навигации для данного хештега. Такая страница содержит ссылки на все публикации, в которых используется данный хештег. В этом смысле хештег работает как входящая ссылка со страницы навигации на сообщение. Каждый хештег обладает семантикой, и обычно его значение слишком узко или слишком общо для того, чтобы охватить смысл всего сообщения. Обычно пост в социальной сети маркируется набором хештегов, при этом все теги поясняют и уточняют друг друга. Чем больше в сообщении подходящих хештегов, тем выше потенциальная привлекательность поста, так как хештег работает как входящая ссылка на сообщение. Однако, вручную подобрать до 30 релевантных хештегов (верхний предел для некоторых крупных социальных сетей) к сообщению может быть очень трудоемко. Цель работы - предложить алгоритм, который облегчит расширение небольшого исходного множества хештегов, подобранного автором публикации. В частности, алгоритм сможет строить ассоциативные ряды хештегов, то есть последовательность семантически связанных хештегов, находящихся между начальным хештегом и конечным хештегом и состоящую из новых хештегов. Два любых хештега из начального набора могут быть использованы в качестве стартового и заключительного хештега для построения ассоциативного ряда, и автор поста может выбрать подходящие хештеги из этого ряда чтобы расширить исходный набор хештегов. 2. Публикации в рассматриваемой проблемной области В различных источниках рассматривается множество задач, похожих на задачу построения ассоциативных рядов хештегов. В [Halliday, Hasan, 1976] рассматривается проблема построения лексических цепочек, которые являются последовательностью семантически связанных слов в тексте. Слово добавляется в цепочку только в том случае, если оно связано с хотя бы с одним словом, уже добавленным в цепочку отношением согласованности (cohesive relation). Типичная задача, в которой могут использоваться такие цепочки, - это сегментация текста, которая впервые была обсуждена в [Morris, Hirst, 1991]. Семантическое расстояние может использоваться в качестве аппроксимации отношения согласованности между словами. Оно может быть рассчитано с помощью одного из двух крупных классов методов: ресурсные меры (resource-based), которые используют ресурсы, похожие на WordNet (применяются в [Barzilay, Elhadad, 1997]); или меры на основе дистрибутивной семантике, такие как word2vec [Mikolov et al., 2013]. Задачи, близкие к задаче построения ассоциативных рядов, часто появляются в области анализа графа знаний. Обычно существует множество путей, соединяющих пару сущностей в графе знаний, и классический подход к выбору оптимального пути - построение кратчайшего пути - широко изучен [Sommer, 2014]. Однако в реальных приложениях наиболее ценными оказываются не просто короткие пути, но короткие и одновременно осмысленные. Эмпирический анализ процесса навигации людей по графу знаний показывает, что люди довольно просто находят интуитивные, но не обязательно кратчайшие, пути в графе знаний. Примеры из [West, Pineau, Precup, 2009] демонстрируют разницу между путями, которые строят люди, и результатами алгоритмов нахождения кратчайших путей: кратчайшие пути оказываются намного менее семантически осмысленными. Это означает, что ограничение на длину пути должно быть ослаблено для того, чтобы допустить более длинные, но более осмысленные пути. В работе [He et al., 2018] авторы называют семантической навигацией процесс навигации от одной сущности к другой на основе семантики сущностей. Пути, которые получаются при помощи семантической навигации, могут быть использованы для того, чтобы связать сущности и выяснить их взаимосвязи. Кроме этого, они могут быть полезны при решении множества прикладных задач, таких как восполнение недостающей информации (knowledge completion) [Neelakantan, Roth, McCallum, 2015] и рекомендация сущностей [Passant, 2010]. Способность вычислять семантическое расстояние может быть использована для построения субоптимального кратчайшего пути, использующего только локальную информацию о структуре сети. Это может позволить значительно снизить вычислительную сложность построения пути в больших сетях [Bringmann et al., 2017]. В [Capitán et al., 2012] авторы показали, что длина таких субоптимальных путей (авторы называют их семантическими путями) была лишь немногим больше, чем длина оптимального решения, когда такой подход был применен к сети статей Википедии. Кроме этого, в работе было показано, что семантические пути намного более семантически связные в сравнении с кратчайшими путями. 3. Методология решения задачи 3.1. Формальное описание задачи Ассоциативные ряды должны быть относительно короткими: желательно, чтобы длина ряда была не более 10 хештегов. Кроме этого, путь не должен иметь больших семантических разрывов: логика каждого перехода должна быть понятной человеку. Желательно, чтобы логика переходов не отклонялась от направления в сторону конечного хештега: каждый очередной хештег в ряду должен быть семантически ближе к конечному хештегу и дальше от начального. Такое свойство можно назвать семантической монотонностью. На рис. 1 представлены примеры ассоциативных рядов, построенных для статей Википедии в работе [Capitán et al., 2012]. Рис. 1. Примеры ассоциативных рядов (из [Capitán et al., 2012]) с семантическими разрывами и без них и отклонениями от направления в сторону семантики конечного хештега Fig. 1. Examples of associative series (from [Capitán et al., 2012]) with and without semantic breaks and deviations from the direction towards the final hashtag semantics Для представленного исследования мы собрали корпус из 14,6 млн сообщений из социальной сети Инстаграм3 (принадлежат организации, признанной в РФ экстремистской). Чтобы избавиться от дубликатов, сообщения с одинаковыми наборами хештегов и идентификаторами пользователей были отфильтрованы. Нашей целью было создание алгоритма построения ассоциативных рядов хештегов, используя сеть совместной встречаемости хештегов. В этой сети хештеги являются узлами. Факт использования пары хештегов в одном сообщении отражается при помощи создания ребра между ними. Мы использовали количество совместных упоминаний в качестве веса связи. Чтобы исключить фактор случайности, мы создавали связь между хештегами только в том случае, если они встречались вместе хотя бы в двух сообщениях. Таким образом мы построили сеть с 1,7 млн узлов (хештегов) и 63,9 млн взвешенных связей. Для построения ассоциативного ряда хештегов при помощи сети совместной встречаемости, необходимо построить путь в сети, который соответствует описанным выше критериям ассоциативных рядов. Такие пути далее мы будем именовать семантическими путями. Дадим постановку задачи построения семантического пути в формальном виде. Пусть P = (n0, n1, ... , nL - 1, nL) - это путь длины L от начальной вершины a(a = n0) к конечной вершине b(nL = b). Расстояние между вершинами обозначим как d(ni, ni + 1) = d i + 1, оно может пониматься как мера семантической близости между двумя соседними хештегами (узлами сети). В этом случае оптимальным семантическим путем можно назвать путь, который не включает больших семантических разрывов, т.е. , где но также путь с наименьшей длиной, т.е. . Таким образом, рассматриваемую проблему построения семантического пути мы постулируем как задачу многокритериальной оптимизации: (1) (2) В этом случае важны оба критерия, но при этом они противоречат друг другу. Путь может быть короче без критерия (1), но будет включать большие семантические разрывы. Путь будет содержать более тесно связанные узлы без критерия (2), но в этом случае он будет слишком длинным и утратит семантическую монотонность. Таким образом важны обе характеристики семантического пути. 3.2. Формулировка обобщенного критерия Чтобы эффективно решить задачу построения семантического пути нам требуется объединить противоречивые критерии (1) и (2). Для этих целей мы создали общий критерий семантического пути, включив в него оба критерия в более гибкой форме, что позволило нам объединить их и скорректировать веса каждого из критериев. На первом шаге рассмотрим критерий (1), который предотвращает большие семантические разрывы. Вместо использования функции максимума в обобщенном критерии мы используем функцию сглаженного максимума Sα, которая стремится к функции точного максимума при параметре α, стремящемся к бесконечности: . Для нашей задачи мы выбрали функцию LogSumExp (LSE) в качестве функции сглаженного максимума: Решая задачу вместо задачи , мы не только уменьшаем семантическое расстояние самого длинного перехода (как это было в случае D(P)), но также семантические разрывы переходов сопоставимой длины. Монотонная функция логарифма и множитель 1/α не влияют на выбор оптимального пути P, поэтому для оптимизации мы можем использовать упрощенную функцию На втором шаге рассмотрим критерий кратчайшего пути (2). Нахождение минимума функции приведет к тому, что путь будет состоять из множества семантически коротких переходов, большая часть которых не способствует приближению к конечному узлу. Чтобы учесть критерий (2), мы добавили штраф d за каждый дополнительный переход в семантическом пути (для удобства мы используем параметр масштаба γ в экспоненте): (3) Функция Wα, d, γ(P) является общим критерием семантического пути с тремя параметрами: α, определяющим штраф за длинные переходы; d, определяющим штраф за каждый дополнительный переход, и γ, который используется для балансировки двух критериев. 3.3. Определение семантического расстояния В формальной постановке задачи построения семантического пути мы предполагали, что существует функция расстояния между узлами d(ni, ni + 1) = d i + 1, которая может пониматься как мера семантической близости. Вместо того, чтобы напрямую использовать веса ребер в сети, мы рассмотрели более продвинутые способы вычисления расстояний, основанные на эмбеддингах (векторном представлении) узлов в пространстве с размерностью векторов порядка нескольких сотен. Этот подход основан на хорошо известных алгоритмах получения векторных представлений слов, таких как word2vec [Mikolov et al., 2013] и GloVe [Pennington, Socher, Manning, 2014]. Векторные представления узлов (хештегов) могут быть интерпретированы как описание их скрытой семантики. Существует два различных подхода, которые позволяют вписать узлы сети в векторное пространство: основанные на топологии сети и основанные на дополнительных свойствах. В [Goyal, Ferrara, 2018] описано более 10 алгоритмов, основанных на топологии сети, которые можно разделить на категории в зависимости от инструмента, который они используют: основанные на матричной факторизации; на случайном блуждании или на глубоком обучении. Несмотря на большое разнообразие инструментов, позволяющих получить эмбеддинги узлов сети на основе ее топологии, мы решили использовать эмбеддинги на основе дополнительных свойств узлов. Поскольку топология сети совместной встречаемости хештегов не была задана изначально, а была получена на основе корпуса сообщений (постов) в социальной сети, мы решили получить эмбеддинги непосредственно на основе данных сообщений. Главным преимуществом такого подхода является прямой доступ к исходным данным вместо получения данных из вторичного источника. Например, работая с сообщениями напрямую, мы имеем возможность учесть близость хештегов в сообщениях. В итоге мы выбрали алгоритм получения эмбеддингов word2vec [Mikolov и др., 2013] со следующими параметрами: размерность векторов - 300, размер скользящего окна (максимальное расстояние между текущим словом и словом из контекста) - 10. Мы использовали вариант skip-gram модели word2vec, поскольку он лучше работает с редкими словами. 3.4. Процедура фильтрации сети совместной встречаемости хештегов Для больших сетей, таких как описанная сеть совместной встречаемости хештегов, нахождение точного кратчайшего пути может оказаться слишком вычислительно сложным. Векторные представления узлов могут быть использованы в качестве быстро работающей эвристики для определения глобального направления к целевой вершине. Это возможно, поскольку, в отличие от расстояний на основе весов связей, расстояние на основе векторных представлений вершин может быть быстро вычислено для любой пары вершин. Узлы с высокой степенью могут создавать трудности для любого алгоритма построения пути. Поэтому мы решили проанализировать распределение степеней узлов. На рис. 2, а показан график распределения степеней узлов в логарифмическом масштабе. Хвост распределения сети совместной встречаемости похож на хвост распределения безмасштабной сети (scale-free network). Это означает, что в сети существуют узлы-хабы, которые представляют популярные хештеги, с очень высокой степенью (105 в нашем случае). Большинство связей с этими хабами семантически слабые, но они значительно увеличивают вычислительную сложность построения семантического пути. Чтобы решить эту проблему, мы решили отфильтровать семантически слабые связи. Для каждого узла ni мы отсортировали связи с его соседями N(i) по убыванию весов связей cij. Затем мы выбрали k верхних связей таким образом, чтобы сумма их весов составила 80% от общей суммы весов связей узла ni: Связи узла ni с меньшими весами, которые не попали в число k верхних соседних узлов, фильтруются. После проведения процедуры фильтрации в сети с 63,9 млн неориентированых связей мы получили сеть с 61,9 млн ориентированных связей. Процедура фильтрации не симметрична в том смысле, что ребро от ni к nj может быть удалена, в то время как ребро от ni к ni может быть сохранено. На рис. 2, b показано распределение исходящих степеней узлов для модифицированной сети в логарифмическом масштабе. После фильтрации степень узлов-хабов снизилась примерно на порядок до 104 связей. Рис. 2. Распределение степеней узлов в сети совместной встречаемости: а - оригинальная сеть; b - сеть после фильтрации слабых связей Fig. 2. Nodes degree distribution of in a co-occurrence network of hashtags in posts: a - original network; b - network after filtering weak ties 3.5. Настройка параметров целевой функции и выбор алгоритмов построения путей Параметры α, d, γ функции Wα, d, γ должны быть настроены перед ее использованием для решения оптимизационной задачи построения семантического пути. Для определения параметра d, который определяет штраф за добавление дополнительного узла в путь, мы использовали распределение семантических расстояний d(ni, nj). Мы вычислили расстояния для всех связанных узлов в сети и нашли четыре квартиля полученного распределения (рис. 3, а). Мы выбрали параметр d равным медиане распределения. В результате добавление каждого нового узла в путь будет увеличивать значение Wα, d, γ на штраф, равный медианному расстоянию между связанными узлами. Для настройки параметров α и γ мы выбрали следующий подход. Мы случайным образом выбрали несколько пар узлов (хештегов) (a, b) из сети совместной встречаемости и построили два пути между ними. Пути первого типа Pa, bdijkstra_hops были получены при помощи алгоритма Дейкстры [Dijkstra, 1959], который минимизирует количество переходов в пути. Пути второго типа Pa, bgreedy_H были получены с помощью простого жадного алгоритма из [Capitán et al., 2012] (рис. 5), который использует семантическое расстояние до целевой вершины в качестве эвристики. Затем мы выбрали α и γ таким образом, чтобы для большинства пар оказалось верным неравенство Wα, d, γ(Pa, bgreedy_H) < Wα, d, γ(Pa, bdijkstra_hops). Использование этих значений параметров для целевой функции Wα, d, γ в алгоритме Дейкстры приводит к тому, что пути второго типа становятся предпочтительнее путей первого типа. Рис. 3. График целевой функции Wα, d, γ со значениями α, γ, для которых Wα, d, γ(Pa, bgreedy_H) < Wα, d, γ(Pa, bdijkstra_hops) для большинства путей. Qi - правая граница i-го квартиля распределения семантических расстояний между связанными вершинами: а - на горизонтальной оси показан промежуток от начала первого квартиля (Q0) до конца четвертого (Q4); b - на горизонтальной оси показан промежуток от начала второго квартиля (Q1) до конца третьего (Q3) Fig. 3. Graph of the objective function Wα, d, γ with values α, γ, for which Wα, d, γ(Pa, bgreedy_H) < Wα, d, γ(Pa, bdijkstra_hops) for most paths. Qi here is the right border of the ith quartile of the distribution of semantic distances between connected vertices: a - the horizontal axis shows the interval from the beginning of the first quartile (Q0) to the end of the fourth (Q4); b - the horizontal axis shows the gap from the beginning of the second quartile (Q1) to the end of the third (Q3) Рис. 4. Жадный алгоритм построения субоптимального кратчайшего пути из [Capitán et al., 2012] Fig. 4. Greedy algorithm for building a suboptimal shortest path from [Capitán et al., 2012] Рис. 5. Жадный top-k-алгоритм: модификация жадного алгоритма из [Capitán et al., 2012] с возможностью хранить k лучших текущих путей Fig. 5. Greedy top-k-algorithm: a modification of the greedy algorithm from [Capitán et al., 2012] with the ability to store k best current paths Построение семантического пути в большой сети, используя алгоритм Дейкстры, может быть слишком вычислительно затратным, поскольку вычислительная сложность алгоритма Дейкстры O(n log (n) + m log (n)), где n - число узлов, m - число ребер в сети. Вместо использования алгоритма, который использует глобальную информацию о сети, мы можем разработать алгоритм, который использует только локальную информацию и эвристику о направлении к целевой вершине, основанную на семантическом расстоянии между узлами. Мы создали такой алгоритм, расширив алгоритм из [Capitán et al., 2012] возможностью хранить k лучших текущих путей. Подробнее наш «жадный top-k-алгоритм» описан на рис. 5. Этот алгоритм представляет собой нечто среднее между простым жадным алгоритмом и хорошо известным алгоритмом A [Hart, Nilsson, Raphael, 1968], который использует эвристику для ускорения алгоритма Дейкстры. 4. Результаты и выводы Наконец, мы использовали целевую функцию Wα, d, γ с двумя выбранными наборами параметров с одним и тем же значением параметра d: α = 5,0; d = 0,55; γ = 0,096 и α = 7,0; d = 0,55; γ = 0,071. Мы использовали эту функцию в двух алгоритмах построения семантических путей на модифицированной сети совместной встречаемости, которая была получена после фильтрации семантически слабых связей. Первый алгоритм - это алгоритм Дейкстры, в котором функция Wα, d, γ использовалась, чтобы взвесить каждое из рассматриваемых ребер. Второй алгоритм - это наш жадный top-k-алгоритм, для которого использовалась функция Wα, d, γ с параметрами d = 0,55; γ = 0,071. Мы взяли два семантически далеких хештега #эконометрика и #лень и построили семантические пути между ними. Результаты применения различных алгоритмов с различными наборами параметров представлены на рис. 6 и 7. Для сравнения мы добавили путь, полученный алгоритмом Дейкстры, который просто минимизирует количество переходов (см. столбец 2) и путь, полученный простым жадным алгоритмом (см. столбец 1). Рис. 6. Пути между начальным узлом #эконометрика и целевым узлом #лень, построенные при помощи различных алгоритмов Fig. 6. Paths between the start node #econometrics and the target node #laziness built using various algorithms Рис. 7. Семантические пути между начальным узлом #эконометрика и конечным узлом #лень, построенные жадным top-k-алгоритмом и алгоритмом Дейкстры с одинаковыми значениями параметров функции Wα, d, γ. Координаты точек для хештегов определяются семантическим расстоянием до начального и конечного узла. Более толстая линия означает более семантически близкую связь Fig. 7. Semantic paths between the start node #econometrics and the end node #laziness, built by the greedy top-k-algorithm and Dijkstra’s algorithm with the same values of the parameters of the function Wα, d, γ. The coordinates of points for hashtags are determined by the semantic distance to the start and end nodes. A thicker line means a more semantically close relationship Как показывают результаты, семантический путь, построенный с помощью специализированных алгоритмов, имеет длину (в количествах переходов) в пределах между длиной кратчайшего пути и длиной пути, полученного при помощи простого жадного алгоритма. Это означает, что эти семантические пути критерию ассоциативного ряда: они относительно короткие. Кроме этого, самый большой семантический разрыв в путях, построенных при помощи специальных алгоритмов, значительно меньше, чем в кратчайших путях, полученных алгоритмом Дейкстры, и даже меньше, чем в пути, построенным жадным алгоритмом. Это означает, что эти семантические пути удовлетворяют и другому критерию ассоциативных рядов: они не имеют больших семантических разрывов. В табл. 1 представлены несколько примеров семантических путей между различными начальным и конечным узлами, построенные алгоритмами, описанными выше. Кроме этих формальных критериев мы можем дать субъективную оценку касательно использования этих путей в качестве ассоциативных рядов. Для всех трех семантических путей (см. рис. 6, столбцы 3, 4 и 5) логика переходов на каждом шаге понятна для человека. Для всех переходов кроме шагов 2 и 3 в столбце 4 наблюдается «семантическая монотонность»: каждый следующий хештег находится семантически ближе к целевому хештегу и дальше от начального. И кроме этого все пути оказались достаточно короткими. Таблица 1 Примеры семантических путей, полученных при помощи различных алгоритмов [Examples of semantic paths obtained using various algorithms] Тип алгоритма [Algorithm type] Пути от исходного узла к целевому [Paths from source node to destination] 1 #небо#самолет#перелет#летимвотпуск#получитьзагранпаспорт#паспорт 2 #небо#самолет#аэропорт#паспорт 3 #небо#поездка#заграница#загранпаспорт#паспорт 1 #красивыеволосы#длинныеволосы#короткиеволосы#рисуноклица#набросок#арт 2 #красивыеволосы#длинныеволосы#арт 3 #красивыеволосы#длинныеволосы#кудряшки#кудряваядевушка#артфото#арт 1 #библиотека#люблючитать#книжнаялюбовь#вынужденныйбрак#романтика 2 #библиотека#роман#романтика 3 #библиотека#роман#романтика 1 #арт#рисую#рисуемвместе#художественноевоспитание#длядетей 2 #арт#длядетей 3 #арт#рисование#детскоеразвитие#длядетей Примечание. Числа над стрелками показывают семантическое расстояние между узлами. [Note. The numbers above the arrows show the semantic distance between the nodes.] 5. Заключение Нами было предложено определение оптимизационной задачи построения семантического пути на сети совместной встречаемости хештегов, которая приводит к построению ассоциативных рядов из хештегов. Кроме этого, наше решение может использоваться более широко для построения ассоциативных рядов любых слов. Для двухкритериальной оптимизационной задачи построения семантического пути мы предложили общую целевую функцию Wα, d, γ. Три параметра этой функции позволяют балансировать критерий минимизации максимального семантического разрыва и критерий минимизации длины пути. Настройка этих параметров была проведена путем применения функции Wα, d, γ к двум различным процедурам построения путей и сравнения результатов на тестовых примерах из реальной сети совместной встречаемости хештегов. Мы собрали информацию об использовании хештегов в одной из крупнейших социальных сетей и построили сеть совместной встречаемости, состоящую из 1,7 млн узлов (хештегов) и 63,9 млн взвешенных связей. После анализа распределения степеней узлов в сети мы оптимизировали структуру связей в сети для дальнейшего использования данной сети в алгоритмах построения семантического пути. Также в этих алгоритмах было использовано семантическое расстояние между узлами (хештегами), полученное на основе алгоритма word2vec. Мы построили примеры семантических путей, используя алгоритм Дейкстры и быстрый жадный алгоритм, и дали субъективную оценку использования этих путей в качестве ассоциативных рядов.

About the authors

Sergey V. Makrushin

Financial University under the Government of the Russian Federation

Email: svmakrushin@fa.ru
Cand. Sci. (Econ.); associate professor Moscow, Russian Federation

Nikita V. Blokhin

Financial University under the Government of the Russian Federation

Email: nvblokhin@fa.ru
teaching assistant Moscow, Russian Federation

References

Supplementary files