Анализ и визуализации сетей соавторства на основе алгоритма кластеризации

Как правило, анализ сетей соавторства начинается с извлечения научных сообществ. Следует сказать, что стандартные силовые алгоритмы [Fruchterman, 1999], [Kamada, 1989] мало пригодны для визуализации научных сообществ, поскольку они стремятся разместить все вершины графа на одинаковом «идеальном» расстоянии. Нам нужен алгоритм, который позволял бы визуально выделять группы исследователей, сильно связанных между собой, и слабо связанных с другими группами. Стандартным способом выделения научных сообществ являются различные методы кластеризации. В нашей системе визуализации был выбран и реализован алгоритм, использующий для оценки качества кластеризации меру модyлярности [Newman, 2004].

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

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

Детальное изображение каждого сообщества строится тоже при помощи силового алгоритма. Но на этом этапе все вершины одной группы располагаются примерно на одинаковом расстоянии друг от друга. Это идеальное расстояние существенно меньше того, что используется при глобальном размещении. Наконец, детальное изображение каждой компоненты подставляется в глобальное размещение компонент и заново отрисовываются все межкомпонентные ребра. На Рис. 1 показан пример изображения наибольшей связной компоненты выделенной из сети соавторства, насчитывающей 2090 авторов. Эта связная компонента имеет 370 вершин и 1690 ребер. На Рис. 1(а) показано изображение этой компоненты при помощи стандартного алгоритма Фрюхтермана-Рейнгольда. На Рис. 1(б) показано изображение этой же компоненты связности при помощи алгоритма, реализованного в нашей системе. В результате применения процедуры кластеризации она была разбита на 35 сообществ. Самое большое сообщество насчитывает 50 авторов. В то же время имеются сообщества, насчитывающие 2−3 исследователя. Обычно каждое такое сообщество формируется вокруг исследователя, имеющего максимальное количество публикаций в данном сообществе. Для того чтобы пользователь мог легко идентифицировать выделенные компоненты, ребра, соединяющие вершины внутри компонент, изображены более широкими линиями чем, ребра, соединяющие вершины разных компонент.

(а) (б) Рис. 1. (а) Изображение сети сотрудничества обычным силовым алгоритмом. (б) Визуализация результатов извлечения сообществ.

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

При выборе на изображении сообществ мышью любой из вершин, идентифицируется кластер, которому принадлежит выбранная вершина. Затем по графу онтологических связей объектов просматриваются все связи вершин-исследователей, принадлежащих этому кластеру с целью выделения общих характеристик исследователей, попавших в один кластер. Количество общих характеристик упорядочивается по убыванию и выдается пользователю. Например, на Рис. 2 показаны общие свойства сообщества, выделенного прямоугольником на Рис. 1. Сообщество состоит из 16 исследователей. Определяющим свойством, по которому был сгенерирован этот кластер, является то, что все указанные исследователи являются авторами одной электронной публикации «Виртуальный музей СО РАН». В силу этого свойства, в сети соавторства была сгенерирована клика, связывающая всех этих исследователей. Следует отметить, что человеческий наблюдатель, знакомый с предметной областью, сразу бы заметил, что все члены этой группы работают в одном институте. Но в данных, внесенных в базу данных информационного портала этой информации нет. В базе данных только для двух человек из этой группы указано место работы, хотя все участники этого кластера работают в одной организации.

Рис. 2. Общие характеристики элементов одного сообщества.

Еще один метод визуализации сетей сотрудничества в комбинации с другими данными, имеющимися в наполнении портала, описан в следующем разделе. Он использует для построения изображения сетей соавторства иерархические жгуты ребер [Holten, 2006].