Кластерный анализ сети цитирования научных журналов

CLUSTER ANALYSIS OF THE CITATION NETWORK OF SCIENTIFIC JOURNALS

Bredikhin S.V., Lyapunov V.M., Shcherbakova N.G.

Institute of Computational Mathematics and Mathematical Geophysics SB RAS

630090, Novosibirsk, Russia

In this work we analyze the structure of the journal citation network built on the basis of the bibliographic information extracted from the database Re.PEc. The network is represented as the weighted directed graph (digraph), the main component G has 1729 vertices (journals) and 135702 arcs (citations). In accordance with M. Ke.ssle.r (1963) the network of bibliographic coupling was constructed that is represented as weighted undirected graph Gbib and in accordance with G. Small (1973), I. V. Marshakova (1973) - co-citation network was constructed that is represented as weighted undirected graph Gcoc. The weights of edges are assigned accordingly vector space model G. Salton, M. MacGill (1983). The graphs G, Gbib h Gcoc are the objects of studying.

In the first part of the work we examine the problem of network connectivity via the adjacency

relations between neighbors. The answer comes in two main flavors. One approach assesses the overall

level of clustering in a network, and is called transitivity, see S. Wasse.rman, K. Faust., (1994). The global

clustering coefficient is the fraction of closed triplets (subgraphs with three nodes and three edges) to

all triplets (subgraphs with three nodes and two edges), see M. Newman (2002). A generalization

to weighted networks was proposed by T. OpsahL P. Panzarasa (2009). An alternative approach to

connectivity was introduced in the work D. Watts, S. Strogatz (1998). A node clustering coefficient is

defined as the fraction of number of actual ties among the neighbor nodes over possible ties between

them. The network local clustering coefficient is defined as an average of clustering coefficients of

nodes and is considered as one of the small-world parameters. For the weighted networks we use the

generalization proposed in the work A. Bar-rat. (2004). The results of local clustering measurements for G Gbib Gcoc

G

Gbib Gcoc

are designed for weighted undirected graphs. We examine applicability of algorithms BTW M. Girvan, M. Newman (2002), WTR P. Pons, M. Latapy (2005), IMP M. RosvalL C. Bergstrom (2008), MLO

G

G

Gbib Gcoc

MLO were applied. Measures for the similarity of partitions delivered by the algorithms were analyzed (NMI, RAND). The results of applying community detection algorithms to graphs G, Gbi^d Gcocare presented in the tables (3.1-3.4).

The conclusion contains comments to the results of the research. The approved tools give the basic-insight about the structure of the bibliometric networks on study.

Key words: journal citation network, co-citation network, bibliographic coupling network, weighted directed graph, transitivity, weighted local clustering coefficient, community finding.

References

1. RePEc. General principles. [Electron. Resource], http://repec.org/.

2. Bredikhin S.V., Lyapunov V.M., Shcherbakova N.G. The structure of the citation network of scientific journals // Problemv informatiki. 2017. № 2. P. 38-52.

3. Harary F. Graph Theory. Addison-Wesley, 1969.

4. Kessler M. M. Bibliographic coupling between scientific papers // American Documentation. 1963. V. 14. P. 10-25.

5. Salton G., MacGill M. J. Introduction to modern information retrieval. N. Y.: McGraw-Hill, 1983.

6. Small H. Co-citation in the scientific literature: A new measure of the relationship between two documents // J. of the American Society for Information Science. 1973. V. 24. P. 265-269.

7. Marshakova I. system of document connections based on references // Scientific and Technical Information Serial of VINITI. 1973. V. 6, N 2. P. 3-8.

8. Watts D. J., Strogatz S. H. Collective dynamics of „small-world" networks // Nature. 1998. V. 393. P. 440-442.

9. Wasserman S., Faust K. Social network analysis: Methods and applications. Cambridge (ENG), New York: Cambridge University Press, 1994.

10. Brandes U. Network analysis. Berlin, Heidelberg, New York: Springer, 2005.

11. Newman M. E. J., Strogatz S. H., Watts D. J. Random graph models of social networks // Proc. of the National Academy of Science of the USA. 2002. V. 99. P. 2566-2572.

12. BollobAS B., Riordan O. M. Mathematical results on scale-free random graphs. Handbook of graphs and networks: Prom genome to Internet. Weinheim, FRG: Wiley-VCH Verlag GmbH k, Co. KGaA, 2002. P. 1-34.

13. Barrat A., Barthelemy XL. Pastor-Satorras R., Vespignani A. The architecture of complex weighted networks // Proc. of the National Academy of Sciences. 2004. V. 101, iss. 11. P. 3747-3752.

14. Lopez-Fernandez L., Robles G., GonzalezBarahona J. Applying social network analysis to the information in cvs repositories // Proc. of the 1st Intl. workshop on mining software repositories (MSR2004). USA: Springer, 2004. P. 101-105.

15. Onnela J.-P., Sarami J., Kertz J., Kaski K. Intensity and coherence of motifs in weighted complex networks // Phvs. Rev. 2005. E 71 065103.

16. Zhang B., Horvath S. A general framework for weighted gene co-expression network analysis // Statistical Applications in Genetics and Molecular Biology. 2005. V. 4., N 17.

17. Opsal T., Panzarasa P. Clustering in weighted networks // Social networks. 2009. V. 31. P. 155-163.

18. Fortunato S. Community detection in graphs // Physics Reports. 2010. V. 486. P. 75-174.

19. Malliaros F. D., Vazirgiannis M. Clustering and community detection in directed networks: A survey // Physics Reports. 2013. V. 533, iss. 4. P. 95-142.

20. Kannan R., Vampala S., Vetta A. On clustering — good, bad and spectral // Foundations of Computer Science. 2000. P. 367-378.

21. Van Dongen S. M. Graph clustering by flow simulation // PhD thesis. University of Utrecht. 2000.

22. Newman M. E. J., Girvan M. Finding and evaluating community structure in networks // Phvs. Rev. 2004. E 69 (2) 026113.

23. Arenas A., Duch J., Fernandez A., Gomez S. Size reduction of complex networks preserving modularity // New J. Phvs. 2007. V. 9, N. 6. P. 176-190.

24. Newman M.E.J. Analysis of weighted networks // Phvs. Rev. E 70, 056131. 2004.

25. Gomez S., Jensen P., Arenas A. Analysis of community structure in networks of correlated data // Phvs. Rev. E 80, 016114.

26. Fred A. L. N., Jain A. K. Robust data clustering // Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR, Minneapolis, USA, June 16-22, 2003. P. 128136.

27. Rand W. M. Objective criteria for the evaluation of clustering methods //J. Amer. Statistical Association. 1971. V. 66, N. 336. P. 846-850.

28. Girvan XL. Newman M. E. J. Community structure in social and biological networks // Proc. Nat. Acad. Sci. USA. 2002. V. 99. P. 7821-7826. *

29. Freeman L. C. A set of measures of centralitv based upon betweenness // Sociometrv. 1977. V. 40. P. 35-41.

30. Rosvall XL. Bergstrom C. T. Maps of random walks on complex networks reveal community structure // Proc. Natl. Acad. Sci. USA. 2008. V. 105, N 4. P. 1118-1123.

31. Rissanen J. Modeling by short data description // Automatica. 1978. V. 14. P. 465-471.

32. Shannon C. E. A mathematical theory of communications // Bell System Tech. J. 1948. V. 27. P. 379-423.

33. Pons P., Latapy M. Computing communities in large networks using random walks // J. of Graph Algorithms and Applications. 2006. V. 10, N 2. P. 191-218.

34. Blondel V., Guillaume J., Lambiotte J., Lepebvre E. Fast unfolding of communities in large networks // J. Stat. Mech. 2008, P10008.

35. Newman M. E. J. Scientific collaboration networks. II. Shortest paths, weighted networks, and centralitv // Phvs. Rev. E 64, 016132. 2001.

36. Brandes U. On variants of shortest-path betweenness centralitv and their generic computation // Soc. Networks. 2008. V. 30. P. 136-145.

37. Jel Classification System / EconLit subject descriptors. 2016. [Electron, resource], https://www .aeaweb .org/econlit/jelCodes .php?view=jel.

38. Bredikhin S.V., Lyapunov V. XL. Shcherbakova N.G. The Structure of the Citation Network of Scientific Journals // Problemv informatiki. 2016. N 3. P. 28-43.

КЛАСТЕРНЫЙ АНАЛИЗ СЕТИ ЦИТИРОВАНИЯ НАУЧНЫХ ЖУРНАЛОВ

Бредихин С. В., Ляпунов В.М., Щербакова Н.Г.

Институт вычислительной математики и математической геофизики СО РАН

630090, Новосибирск, Россия

УДК 001.12—303.2

Изучается сеть цитирования научных журналов, представленная взвешенным ориентированным графом. Основное внимание сфокусировано на проблемах связности и выявлении модульной структуры сети. Рассмотрены методы анализа объектов сетевой структуры. На основе реальных библиографических данных, извлеченных из БД RePEc [1], построены плавная связная сетевая компонента G и производные сети: коцитирования — Gcoc и библиографического сочетания - Gblb. Для этих сетей измерены локальный и взвешенный коэффициенты кластеризации. Выявление модульности рассматривается как задача идентификации структурно эквивалентных вершин соответствующих графов. С применением алгоритмов BTW,

G

таты представлены в виде рисунка и таблиц. Сравнение результатов осуществлено с помощью индексов согласованности NMI и RAND.

Ключевые слова: сеть цитирования научных журналов, сети коцитирования и библиографического сочетания, взвешенный ориентированный граф, локальный взвешенный коэффициент кластеризации, выявление сообществ.

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

1.1. Сеть цитирования журналов (СЦЖ), На множестве журналов J = {J1, J2,..., Jn} задано отношение цитирования R:

СЦЖ представляет орграф С = (У,Е), в котором журналы соответствуют вершинам V = {^1, у2,..., гп}, а цитирования — дугам Е С V х V, е = (ь^, ) € Е, если выполняется (1.1). Если г = то отношение (1.1) называется самоцитированием. На множестве дуг определена функция ю : Е ^ такая что ю(е) = ю^ равна числу цитирований, полученных журналом ] от журнала г. Матрица цитирований А графа С имеет размер IV| и содержит элементы:

JkRJl = Jk цитирует Ji.

A(i,j) = {

1, если iRj,

0, в противном случае.

Матрица весов W дуг графа G имеет размер |V| и содержит элементы:

ш^) Г ^,

^ 0, в противном случае,

СЦЖ соответствует слабо связный [3] взвешенный орграф С = (У,Е),|У| = 1729, |Е| = 135702 (без учета самоцитирований и изолированных вершин). Максимальная силь-

С

1,2, Сеть библиографического сочетания журналов (СБСЖ) построена на основе СЦЖ, Метод „библиографического сочетания" [4] был распространен на множество журналов, Говорят, что журналы гну находятся в состоянии библиографического сочетания, если существует журнал к, па который ссылаются г ж у.

гКЫЬ] =

СБСЖ соответствует взвешенный граф СЬгЬ, множество вершин которого совпадает с V. Отношения ЯЬгЬ между вершинами выступают в роли неориентированных связей (ребер) Е С V х V, е = (гу) € Е, если имеет место г ВЬгЪу Журнал г представляется вектором (строкой) матрицы Ш. Для определения веса ребер графа СЬгЬ используется векторная модель [5], а степень подобия ЫЪ(гу) вычисляется следующим образом:

Е шгк ы^к

ЪгЪ

,/Е

к

Матрица смежности Сы\ соответствующего СБСЖ, обозначается ШЬгЬ. В качестве графа СЬгЬ = (УЬгЬ,ЕЬгЬ^ рассматривается его максимальная связная компонента, ^ЬгЬ| = 1432 (остальные 297 вершин являются одиночными), |ЕЬгЬ| = 844476 ребер,

1,3, Сеть коцитирования журналов (СКЦЖ) также построена на основе СЦЖ, Для

"

г и у находятся в отношении коцитирования Ксос, если существует журнал к, содержащий ссылки на журналы г и у т. е.

гЯсосу =

Ссос

с V. Отношения Ясос между вершинами выступают в роли неориентированных связей (ребер) Е С V х V,e = (гу) € Е, если имеет место г Ясос у Журнал г представляется вектором (столбцом) матрицы Ш. Используя векторную модель, степень подобия сос(г, у) определим так:

Е ЫкгЫк]

СОС

Матрица смежности взвешенного неориентированного графа, соответствующего СКЦЖ, обозначается Шсос. В качестве графа Ссос = (Vсос,Есос) рассматривается его максимальная связная компонента IVсос| = 1582 (остальные 147 вершин являются одиночными), |Есос| = 820982

гС

С

соседями. Это локальное свойство вершины получило название „локальный коэффициент

""

чепия. Определение коэффициента для невзвешенных графов без кратных ребер и петель приведено в работе [8]. Параметр характеризует степень связности графа,

2.1. Локальный коэффициент кластеризации ОО

ООп= 2Ег = Щк) € Е : у,к € Мг}1 = ^^^

Для орграфа максимально возможное число ребер между соседями равно кг

Ег

ОО« = кМ ^

Локальный коэффициент кластеризации ОО (С) граф а С определяется как среднее

ОО

ОО

г

ОО

„малого мира", которая характеризуется малым „средним расстоянием" Ьаид(С) [2] меж-

ОО

Яаид (С) медленно (логарифмическая зав исимость), а ОО (С) — быстро,

2.2, Альтернативный подход к определению связанности соседей представлен в работе [9], где введено отношение транзитивности между вершинами графа. Рассмотрим случай неориентированных графов. Отношение Т обладает свойством транзитивности, если для любых г,у,к го того, что гТу и уТк., следует гТк. Для вершин это обозначает, что пути длины два замкнуты. Для примера укажем, как это свойство выполняется для всех путей длины два. Такие пути можно представить с помощью матрицы А2, где А — матрица смежности С. Путь из г в у замкнут, если имеет место: А^- ^ 1 & А^ = 1,

В работе [10] относительная транзитивность графа выражается через треугольники и тройки вершин. Треугольник А = {"^д, Ед} — это полный подграф графа С, множество

С

гг

г

,л гф,д{г) deg{i)2 - йедЦ) т(i) = С2д(' =-2-.

Число всех троек в графе С определяется суммой т(С) = Е т(-) и совпадает с чис-

г

лом путей длины два. Обозначим через А(С) число треугольников графа С. Определим А(-) = ||Д| : i € — число треугольников, в которых - является одной из вершин.

Заметим, что А(С) = 1/3 У] А(г). В этих терминах (2.1) выглядит как СС(г) = —7-). Пусть

г т

V' = {г : ¿вд(г) > 2}, тогда СС (С) = Е СС (г).

1V 1 геУ

Глобальный коэффициент кластеризации графа (транзитивность), явно определенный в работе [11], задается равенством:

число треугольников 3—

Т

число троек т

Отсюда 0 ^ Т(С) ^ 1, Заметим, что число треугольников можно вычислить как сумму диагональных элементов матрицы А3, а по матице Л2 можно определить число троек.

Равенство, демонстрирующее разницу между локальным и глобальным коэффициентами кластеризации, приведено в работе [12]:

Е т

т

Е т

геУ'

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

Понятие локального коэффициента кластеризации расширено для случая взвешенной сети в работе [13], Для взвешенных графов в формуле участвует сила, связей вг вершины которая для неориентированного графа определяется с помощью матрицы Ш как:

п

вг = ^2 Ыгу.

3=1

Соответственно, взвешенная, степень вершины, неориентированного графа на основе

вг

„силы связей" определяется из выражения йед™ (-) = ———.

¿вд

Взвешенный локальный коэффициент кластеризации узла - (неориентированный случай) определяется так:

СС-

г з,ь

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

элемент вг(кг — 1) вычисляет вес всех инцидентных ребер, умноженный на максимальное число треугольников с вершиной г, т, е, 0 ^ ООт(г) ^ 1,

Взвешенный локальный коэффициент кластеризации графа определяется следующим образом:

ООт

г

Отметим, что если Угу тгз = 1, то результаты (2,3) и (2,8) совпадают. Как замечено в работе [13], в реальных сетях, если имеет место неравенство ООw (С) > ОО (С), то наиболее вероятно, что треугольники образуются ребрами с большими весами, если О О (С) > О Оw (С), то топологическая кластеризация свойственна ребрам с маленькими весами. Другие подходы к определению локального коэффициента кластеризации для случая взвешенной сети можно найти в работах [14-16],

В работе [17] определен обобщенный глобальный коэффициент кластеризации как:

общий вес треугольников

Т^т

т

общий вес троек

Вес тройки определяется в зависимости от особенностей сети, так для сети, в которой

"

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

±т — ^

2,3, Результаты измерения коэффициентов кластеризации.

2,3,1, Локальный коэффициент кластеризации СЦЖ, Для вычисления взвешенного локального коэффициента кластеризации ООт орграф С был преобразован в неориентированный Си следующим образом. Если между вершинами г ж у имеется только одна взвешенная дуга (гу^и (уг), то дуга преобразуется в ребро (гу), которому присваивается вес, равный весу дуги; если между вершинами г и у имеются две дуги (гу) и (у,г), то обе они преобразуются в одно ребро (г, у), которому присваивавтея вес тгз + равный сумме весов дуг. Значение ООт(Си) = 0,64170 получено с помощью пакета гдгарк (согласно (2,7), (2,8)), сложность вычислений оценивается как О (IV |теап(^ед(.))2), Отметим, что

Си

ции считается неопределенным; у 1,7% вершин соседние вершины не имеют между собой связей, для них ООт(г) = 0, Заметим, что если веса ребер нормализовать, например, путем

тгз

деления веса ребра на средний вес ребра в графе тгз = —-т——, значение коэффициента

¿2шгз/|Е 1

гз

изменится, ООт(Си) = 0,48463,

Для вычисления коэффициента кластеризации невзвешенного графа, согласно (2,3), орграф Си был преобразован (Сипт), в результате: независимо от того, имеется между гу

ние параметра ОО(С'аапт) = 0,54594,

60

50 -40 -30 -20 -10 -

0

о

О ООО

>°° о°

о

ООО

О о о о

п%0

о о оо^о

оо о

оо

п поста]

0,25 0,5 0,75 1,0

Рис. 2.1. Распределение СС™(г) графа С. На оси абсцисс указаны абсолютные значения коэффициента; на оси ординат — число вершин, для которых х ^ СС™(г) ^ х + 0,01

Е

Для уточнения зависимости между взвешенными степенями вершин йвд'ш (г) = -—— и

йед

взвешенными локальными коэффициентами кластеризации вычислен коэффициент ранговой корреляции Спирмена, его значение г = -0,352 говорит о том, что, несмотря на выполнение неравенства СС™(Си) > СС(С™™), для вершин с небольшой взвешенной степенью более характерно наличие взаимосвязанных соседей. Распределение взвешенных коэффициентов кластеризации представлено па рис. 2.1, па котором пе представлены вершины с нулевым коэффициентом и вершины с максимальным значением, равным единице (48 вершин).

2.3.2. Локальный коэффициент кластеризации СБСЖ, Вычислены коэффициенты кластеризации для взвешенного и невзвешенного вариантов: СС™(СЪгЪ) = 0,80156 (2.7, 2.8); ССипш(СЪгЪ) = 0,77971 (2.3). Отметим, что 18,5% вершин СЪгЪ имеют менее двух соседей, дня них значение коэффициента кластеризации считается неопределенным. Разница между коэффициентами СС™ и ССиаш невелика. Коэффициент ранговой корреляции Спирмена, оценивающий зависимость между взвешенными степенями вершин и взвешенными локальными коэффициентами кластеризации, имеет значение г = -0,322.

2.3.3. Локальный коэффициент кластеризации СКЦЖ. Коэффициенты кластеризации для взвешенного и невзвешенного вариантов графа Ссос : СС™(Ссос) = 0,82860; ССиаш(Ссос) = 0,80588. При этом 9,3 % вершин Ссос имеют менее двух соседей, для них значение коэффициента кластеризации считается неопределенным. Разница между коэффициентами дня взвешенного и невзвешенного вариантов невелика. Коэффициент ранговой корреляции Спирмена, оценивающий зависимость между взвешенными степенями вершин и взвешенными локальными коэффициентами кластеризации, имеет значение г = -0,266.

3. Кластерный анализ. Широко используемый в прикладных исследованиях метод кластерного анализа (КА, или кластеризация) состоит в выявлении модульной структуры некоторого непустого множества объектов. Основой К А является группирование объектов па основании подобия их параметров. В пашем случае объектами являются научные жур-

налы, размещенные в одной БД, Кластеризация О = {О1, ... ,Ок} граф а С = (У,Е) — это разбиение множества вершин V на желательно непересекающиеся непустые подмножества (кластеры) Ог. Разбиение множества вершин индуцирует разделение множества ребер. Обозначим Е(Ог) множество ребер, ориентированных из Ог в О^ Е(Ог,Ог) (сокращенно Е(Ог)), — множество ребер, связывающих вершины кластера Ог. Тогда Е(О) := ик=1Е(Ог) является множеством внутриклаетерных ребер, а Е\Е(О) — множеством внекластерных ребер. Кластер будем идентифицировать с подграфом графа С, т. е. С[Ог] := (Ог,Е(Ог)).

к = 1 к = п

к=2

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

Кластеры, строящиеся на отношении подобия, отличном от плотности, учитывающем свойства самих узлов, например сходство их относительных позиций в сети, выявляют структуры с интересными свойствами коннективности. Для сетей цитирования это могут быть кластеры, строящиеся на отношении коцитирования (структурные свойства вершин кластера: являются конечными вершинами ребер, ведущих из одной и той же начальной вершины) или библиографического сочетания (структурные свойства вершин кластера: являются начальными вершинами ребер, ведущих в одну и ту же конечную вершину), К одной и той же сети могут быть применимы обе модели кластеризации. Обзор концепций, методов и алгоритмов, применяемых для кластеризации графов, можно найти в работах

Для проверки качества деления на кластеры в предположении, что истинные группы не известны, разрабатываются индексы качества кластеризации, В этом вопросе консенсус также не достигнут. Определения индексов, построенных на соотношении внутри и вне кластерных связей, можно найти, например, в работах [20, 21], Распространенным способом проверки является вычисление параметра „модульность", определенного в работе [22], Определение строится в предположении, что структура графа, содержащего некие сообщества вершин, как правило, будет отклоняться от структуры случайного графа, Оценивается, насколько доля ребер между вершинами одного типа (т, е, попавших в один кластер) отличается от ожидаемой доли таких ребер в том случае, если ребра располагаются случайным образом, независимо от типа вершин. Для неориентированного графа параметр (нормализованная) модульность вычисляется по формуле:

где кг — степень верш ины г, 5(Ог,Оз) = 1, есл и Ог = Оз, и 5(Ог,Оз) = 0 в противном случае,

"

[18, 19].

гу

В работе [23] определение модульности расширено для орграфа:

л -сиг -Ли \

Qd = -Е - ¿

где -°и1 — исходящая степень вершины г, —га — входящая степень вершины ].

Для взвешенных графов с положительными весами в работе [24] предложено пользоваться формулами (3,1), (3,2), где А — взвешенная матрица смежности. Если используется

отдельная матрица весов = Е № = Е №3, т0 формула (3,1) будет иметь вид:

з г,3

Qu = 2№ Е - ^ тс). ад

Подход к определению модульности при наличии отрицательных весов представлен в работе [25],

Для сравнения результатов кластеризации одного и того же множества данных различными алгоритмами разработан ряд критериев, В нашем случае используются два индекса (меры) согласованности. Индекс NМ1, представленный в работе [26], определяет степень согласованности двух делений на кластеры на основе понятия взаимной информации, используемой в теории вероятностей. Пусть имеется п объектов и два результата разделения на кластеры: А с кластерами ,..., и В, с кластерами О^, О^,..., Ов, Инфор-

А

к А / А4

пА / пЛ

H(A) = ^ log ^

£-/ Т) \ п

П \ n

г=1

где nA — число элементов в кластере CA, Рассмотрим матрицу соответствия NAB размерности k х /, номера строк которой соответствуют номерам кластеров разделения A, столбцов — номерам кластеров разделения Б, элемент NAB = |CA П CB| — число объектов, общих для кластеров CA и CB, Индекс NMI(А,Б) определяется равенством

Д' ^ (NAB х n

- 2 S S j 4 NANf,

NMI

E NA log -U + E NjB log nL

г=1 \ n J г=1 j \ n

NiA NiB NAB

Индекс RAND (R), представленный в работе [27], определяет долю согласованных пар кластеризуемых объектов по отношению ко всем парам. Пусть а — число пар, находящихся в одном кластере при делении А и делении Б; b — число пар, находящихся в разных кластерах при делении А и при делении Б; c — число пар, находящихся в одном кластере при делении А и в разных при делении Б; d — число пар, находящихся в одном кластере при делении Б и в разных при делении А, Тогда

а + b а + b

ЙА™(А-Б >= а + b + c + d = "CT

n

NAB

N AB у •

у2

RAND(A,B) =-—

СП + 2Е Е C2ij

nA . A ^NB 2

ECn + £ С2'j

2

С

3,1, Алгоритмы кластеризации. Следует заметить, что большинство определений и алгоритмов выявления сообществ предназначены для неориентированных невзвешенных графов, В нашем случае вес ребра является показателем силы связей узлов, которую следует учитывать. Рассмотрим четыре алгоритма выявления сообществ для взвешенных графов,

3.1.1, Иерархический алгоритм BTW., предложенный в работе [28], базируется на предположении, что меры центральности сетевых акторов могут использоваться для классификации узлов сети. Предлагаемый алгоритм основан на параметре „реберная центральность по посредничеству" [29], Параметр учитывает долю кратчайших путей между парой вершин, проходящих через данное ребро:

Св

i=jev ij

где Oij — число кратчайших путей от вершины г до вершины j графа, a aj (e) — число кратчайших путей от г до j, проходящих через ребро е. Предполагается, что ребра между сообществами имеют большее значение параметра. Основной цикл алгоритма выглядит

e

Св(е); 3) вычисляется значение модульности (3.2)—(3,3); 4) цикл повторяется. Таким образом, исполняется иерархическая процедура разделения. Лучшим считается уровень, соответствующий наибольшему значению модульности. Алгоритм используется как для неориентированных, так и для орграфов, сложность алгоритма оценивается как O(|V||E|2),

3.1.2, В работе [30] рассматривается влияние структуры сети на сетевые потоки. Метод кластеризации использует информационную стоимость описания свободного блуждания по сети (или движения потоков) при различных делениях акторов на сообщества и связан с принципом минимального описания, формализованным в работе [31] и заключающимся в том, что лучшая гипотеза по поводу структуры данных та, которая ведет к большей компрессии данных. Оценивается нижняя граница кода L(M), соответствующего разделению M = {Ml,M2,... ,Mk} имеющихся n вершин на k кластеров, который учитывает энтропию свободного блуждания внутри и вне кластера и базируется на теореме Шеннона

n

случайной переменной через ее энтропию. Соответствующий базовый алгоритм IMP для неориентированных графов [30] состоит из двух этапов. Первоначально каждая вершина является кластером. На первом этапе случайным образом вершина объединяется с раз-

L

перестраивается так, что каждый кластер становится вершиной. Процесс повторяется до L

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

3.1.3, Подход, также основанный на процессе случайного блуждания, используется в работе [33]. Представленный алгоритм WTR выявляет плотные подграфы исходного графа, На начальном этапе считаем, что каждая вершина является кластером. Основной цикл

Таблица 3.1

Кластеризация орграфа G алгоритмом IMP [30]

ФС1 *J Тематика

1 675 Финансовая экономика, обзорные журналы по экономике, математические и количественные методы

1 160 Администрирование и экономика бизнеса, маркетинг, бухучет

1 139 Евроэкономика

1 131 Экономика сельского хозяйства и природных ресурсов

1 80 Транспортная экономика, математические и количественные методы

1 62 Здравоохранение, социальное обеспечение

1 60 Эконометрические и статистические методы

1 54 Региональная экономика

1 35 Энергетика

1 22 Математические и количественные методы

1 20 Чехия

1 19 Польша

1 14 Восточная Европа

2 13 Социальное обеспечение, немецкоязычные журналы

3 10 Администрирование и экономика бизнеса

2 9 Болгария, регулирование

Применение. Здесь и далее: фС1 — число мастеров, фJ — число журналов в кластере

алгоритма выглядит так: 1) вычисляются „расстояния" между всеми соседними кластерами; 2) по критерию „расстояния" выбираются два соседних кластера; 3) они объединяются в новый кластер и выполняется переход к шагу (1). Этот цикл повторяется (|V| — 1) раз. Для определения качества разбиения вычисляется модульность. Вычислительная сложность алгоритма равна O(|E| |V|2). Для разреженных сетей вычислительная сложность оценивается как O (| V |2 log (| V |).

3.1.4. Иерархический алгоритм MLO, основанный на оптимизации модульности, предложен в работе [34]. Первоначально предполагается, что каждая вершина графа образует кластер. Алгоритм состоит из повторяющихся шагов, каждый шаг состоит из двух фаз.

Фаза 1. Для каждой вершины г рассматривается перемещение в кластер C, соответствующий ближайшему соседу j, Вычисляется изменение модульности при перемещении вершины г в кластер C. Проверяются все ближайшие соседи г, перемещение происходит в тот кластер, которому соответствует наибольшее увеличение модульности. Если улучше-г

пока возможно улучшение. Первая фаза заканчивается достижением локального максимума модульности.

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

Фазы 1-2 повторяются до тех пор, пока невозможны новые изменения. Число кластеров существенно уменьшается с каждым шагом. Сложность алгоритма в применении к разреженным графам составляет O(|E|).

3,2, Результаты, кластеризации.

3.2.1, Кластеризация СЦЖ. Кластеризация орграфа G производилась с помощью алгоритмов IMP и BTW. В результате кластеризации G алгоритмом IMP было получено 20 кластеров размером 9 и более вершин (89,35%), Остальные 97 кластеров имеют меньшее число вершин. Результаты проверки кластеризации алгоритмом IMP показала, что кластеры средних размеров выявляют сообщества журналов, публикующих, в основном, статьи, относящиеся к определенным тематикам или территориальным группам. Наблюдаемая тенденция: у кластеров с числом вершин, большим 22, число вершин, у которых есть исходящие дуги, ведущие из кластера (шлюзы), меньше, чем число вершин, к которым есть входящие извне дуги; такое же распределение у суммарного веса соответствующих дуг, У небольших кластеров наоборот: суммарный вес выходящих из кластера дуг больше, чем входящих, т, е, небольшие кластеры представляют собой более замкнутые тематические сообщества. Результаты приведены в табл. 3,1,

Алгоритм BTW основан на подсчете кратчайших путей, поэтому вместо весов дуг Wj использовались обратные значения 1/wj (см. [35]). В результате кластеризации графа G получен один кластер размером 1242 вершины, что составляет 71,83% вершин. Остальные 483 кластера имеют 4 и менее вершин, большинство из них одновершинные. Индексы согласованности кластеризации G алгоритмами IMP и BTW-. NMI = 0,23; Rand = 0,44,

G

Wij = wmax +1 — Wj, где wmax - максимадьный вес дуг графа G. Результаты кластеризации изменились: наибольший кластер содержит 1522 вершины (80,02%), остальные содержат 3 вершины и менее. Более того, подобный результат получился и при применении алгоритма BTW к невзвешенному орграфу Gunw: большинство вершин попали в один большой кластер (87,85%), Можно предполагать, что в нашем случае алгоритм нечувствителен к масштабу весов дуг.

Для неориентированного варианта графа цитирования Gu (см, 4,1,1) рассмотрены четыре алгоритма кластеризации: BTW, IMP, WTR и ML О. При кластеризации Gu алгоритмом BTW вновь получилась практически тривиальная кластеризация: 86% вершин попали в один кластер, наибольший процент остальных — в одиночные кластеры. Распределение размеров кластеров, полученных в результате работы остальных алгоритмов, представлено в табл. 3,2,

Индексы согласованности результатов кластеризации Gu выглядят так: NMI = 0,52, RAND = 0,84 для WTR и MLO; NMI = 0,62, RAND = 0,86 для IMP и MLO; NMI = 0,58, RAND = 0,86 для IMP и WTR. Согласованность алгоритма IMP в применении к графам G и Gu\ NMI = 0,54; RAND = 0,82, — т. е, сравнима с кластеризацией

Gu

стеров, тематические области сходны. Области определялись на основании названий журналов, тематика сопоставляется согласно большинству в процентном отношении. Следует отметить, что для журналов издательства Elsevier (153 журнала) в базе данных указаны коды тематик согласно классификационной системе J el [37], Анализ показал, что коды журналов издательства Elsevier соответствуют установленным тематикам кластеров, в которые они попали. При этом установленная тематика в большинстве случаев относится к основным тематикам (general categories) по классификации J el. Тематические группы,

Gu

3.2.2, Кластеризация Gblb. Алгоритм IMP объединил все 1432 вершины в один кластер, т. е, не установил дополнительного подобия уже подобных согласно отношению Rblb вер-

Таблица 3.2 Распределение размеров кластеров при кластеризации графа Gu

IMP [30] WTR [33], Qu = 0,42 MLO [34], Qu = 0,43

ФС1 *J фС1 *J фС1 *J

1 737 1 657 1 585

1 186 1 284 1 395

1 158 1 268 1 226

1 136 1 221 1 178

1 95 1 75 1 104

1 65 1 62 1 100

1 60 1 44 1 85

1 59 2 8 1 54

1 48 1 1 1 2

1 38

1 35

1 32

1 15

1 14

1 12

1 9

3 4

2 3

6 2

шин. Размеры кластеров, полученных с применением алгоритмов И'77t' и MLO, приведены в табл. 3.4.

Согласованность WTR и MLO: NMI = 0,79; RAND = 0,84. Если сравнить кластеры WTR (30 вершин) и MLO (70 вершин), то в первом кластере 67% журналов относятся к статистическим исследованиям, а во втором 46 % таких журналов, причем все 30 журналов первого кластера содержатся во втором, 24% журналов относятся к эконометрии.

3.2.3. Кластеризация Gcoc. Использованы алгоритмы, приведенные в п. 3.2.2. Алгоритмом IMP получена тривиальная кластеризация. Размеры кластеров, полученных с применением алгоритмов WTR и ML О, приведены в табл. 3.5.

Кластеризация с помощью алгоритмов WTR и ML О получена при значении модульности Q = 0,16 и Q = 0,21 соответственно; согласованноеть: NMI = 0,64; RAND = 0,82.

Заключение. Проанализированы библиометрические сети, акторами которых являются журналы, проиндексированные в базе данных RePEc. Они представлены плотными графами, имеющими большие значения коэффициентов кластеризации, независимо от того, учитываются ли веса ребер. Выявление сообществ с помощью алгоритма IMP в применении к взвешенному орграфу цитирования позволило выявить сообщества журналов, тесно связанных по тематическому или территориальному признаку Алгоритм BTW не дал явных результатов ни в применении к орграфу цитирования, ни к его неориентированному представлению. В то же время результаты алгоритмов IMP, WTR и MLO в применении к неориентированному взвешенному графу имеют достаточный уровень со-

Таблица 3.3

Тематика кластеров при кластеризации Gu алгоритмом IMP

41(~ч тг^1 #j Тематика

1 737 Финансовая экономика, математические и количественные методы

1 186 Администрирование и экономика бизнеса, маркетинг, бухучет

1 158 Финансовая экономика

1 136 Экономика сельского хозяйства и природных ресурсов

1 95 Румыния

1 65 Эконометрические и статистические методы

1 60 Здравоохранение, социальное обеспечение

1 59 Исследование операций

1 48 Региональная экономика

1 38 Энергетика

1 35 Транспортная экономика, математические и количественные методы

1 32 Администрирование и экономика бизнеса, маркетинг, бухучет

1 15 Восточная Европа

1 14 Жилищная и имущественная политика

1 12 Не идентифицирован

1 9 Образование

Таблица 3.4 Кластеризация графа Gbib

WTR [331, Qu = °Д3 MLO [341, Qu = 0,15

ФС1 *J ФС1 *J

1 718 1 541

1 369 1 514

1 288 1 307

1 30 1 70

1 25

2 1

Таблица 3.5

Кластеризация графа Gcoc

WTR [331, Qu = 0,13 MLO [341, Qu = 0,15

ФС1 *J ФС1 *J

1 517 1 410

1 350 1 391

1 255 1 369

1 235 1 315

1 32 1 97

1 30

1 9

9 < 9

гласованности, особенно соответственно индексу RAND. Во всех трех случаях получился один большой кластер, содержащий более 33 % вершин; остальные вершины распределены по сообществам, причем алгоритм MLO выделил наибольшее число сообществ. Сравнение результатов кластеризации алгоритмом IMP в применении к орграфу цитирования и неориентированному графу показало, что, несмотря на различие в размерах кластеров и распределении вершин по кластерам, определены сходные тематики. Таким образом, неориентированный вариант графа вполне можно использовать для выявления тематик.

Размер кластеров, полученных в результате кластеризации СЬгЬ и Осос, слишком большой, чтобы соотнести их с тематическими группами, однако согласованность примененных алгоритмов достаточно высокая. Следует заметить, что кластеризация сетей библиографического сочетания и коцитирования, акторами которых являют-

ся публикации из рассмотренных здесь журналов [38], была получена с применением алгоритма ML О при больших значениях модульности и большей степени согласованности.

Список литературы

1. RePEc. General principles. [Electron, resource], http://repec.org/.

2. Бредихин С. В., Ляпунов В. \!.. Щербакова Н. Г. Структура сети цитирования научных журналов // Проблемы информатики. 2017. № 2. С. 38-52.

3. Harary F. Graph Theory. Addison-Wesley, 1969.

4. Kessler M. M. Bibliographic coupling between scientific papers // American Documentation. 1963. V. 14. P. 10-25.

5. Salton G., MacGill M. J. Introduction to modern information retrieval. N. Y.: McGraw-Hill, 1983.

6. Small H. Co-citation in the Scientific Literature: A New Measure of the Relationship Between Two Documents //J. of the American Society for Information Science. 1973. V. 24. P. 265-269.

7. Marshakova I. System of document connections based on references // Scientific and Technical Information Serial of VINITI. 1973. V. 6, N 2. P. 3-8.

8. Watts D. J., Strogatz S. H. Collective dynamics of „small-world" networks // Nature. 1998. V. 393. P. 440-442.

9. Wasserman S., Faust K. Social network analysis: Methods and applications. Cambridge (ENG), New York: Cambridge University Press, 1994.

10.Brandes U. Network analysis. Berlin, Heidelberg, New York: Springer, 2005.

11.Newman M. E. J., Strogatz S. H., Watts D. J. Random graph models of social networks // Proc. of the National Academy of Science of the USA. 2002. V. 99. P. 2566-2572.

12.bollobas В., Riordan О. M. Mathematical results on scale-free random graphs. Handbook of graphs and networks: Prom genome to Internet. Weinheim, FRG: WTilev-VCH Verlag GmbH k, Co. KGaA, 2002. P. 1-34.

13. Barrat A., Barthelemy XL. Pastor-Satorras R., Vespignani A. The architecture of complex weighted networks // Proc. of the National Acad, of Sci. 2004. V. 101, iss. 11. P. 3747-3752.

14. Lopez-Fernandez L., Robles G., Gonzalez Barahona J. Applying social network analysis to the information in cvs repositories // Proc. of the 1st Intl. workshop on mining software repositories (MSR2004). USA: Springer, 2004. P. 101-105.

15. Onnela J.-P., Sarami J., Kertz J., Kaski K. Intensity and coherence of motifs in weighted complex networks // Phvs. Rev. 2005. E 71 065103.

16. Zhang В., Horvath S. A general framework for weighted gene co-expression network analysis // Statistical Applications in Genetics and Molecular Biology. 2005. V. 4., N 17.

17. Opsal Т., Panzarasa P. Clustering in weighted networks // Social networks. 2009. V. 31. P. 155-163.

18. Fortunato S. Community detection in graphs // Physics Reports. 2010. V. 486. P. 75174.

19. Malliaros F. D., Vazirgiannis M. Clustering and community detection in directed networks: A survey // Physics Reports. 2013. V. 533, iss. 4. P. 95-142.

20. Kannan R., Vampala S., Vetta A. On clustering — good, bad and spectral // Foundations of Computer Science. 2000. P. 367-378.

21. Van Dongen S. M. Graph clustering by flow simulation // PhD thesis. University of Utrecht. 2000.

22. Newman M. E. J., Girvan M. Finding and evaluating community structure in networks // Phvs. Rev. 2004. E 69 (2) 026113.

23. Arenas A., Ducn J., Fernandez A., Gomez S. Size reduction of complex networks preserving modularity /7 New .J. Phvs. 2007. V. 9, N. 6. P. 176 190.

24. Newman M. E. .J. Analysis of weighted networks /7 Phvs. Rev. E 70, 056131. 2004.

25. Gomez S., Jensen P., Arenas A. Analysis of community structure in networks of correlated data /7 Phvs. Rev. E 80, 016114.

26. Fred A. L. N., Jain A. K. Robust data clustering /7 Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR, Minneapolis, USA, .June 16 22, 2003. P. 128 136.

27. Rand W. M. Objective criteria for the evaluation of clustering methods /7 .J. Amer. Statistical Association. 1971. V. 66, N. 336. P. 846 850.

28. Girvan M., Newman M. E. .J. Community structure in social and biological networks /7 Proc. Nat. Acad. Sri. USA. 2002. V. 99. P. 7821 7826.

29. Freeman L. C. A set of measures of centralitv based upon betweenness /7 Sociometry. 1977. V. 40. P. 35 41.

30. Rosvall M., Ber.gstr.om С. T. Maps of random walks on complex networks reveal community structure /7 Proc. Natl. Acad. Sri. USA. 2008. V. 105, N 4. P. 1118 1123.

31. Rissanen J. Modeling by short data description /7 Automatica. 1978. V. 14. P. 465 471.

32. Shannon C.E. A mathematical theory of communications /7 Bell System Tech. .J. 1948. V. 27. P. 379 423.

33. Pons P., Latapy M. Computing communities in large networks using random walks /7 .J. of Graph Algorithms and Applications. 2006. V. 10, N 2. P. 191 218.

34. Blondel V., Guillaume J., Lambiotte J., Lefebvre E. Fast unfolding of communities in large networks /7 .J. Stat. Meeh. 2008, P10008.

35. Newman M. E. .J. Scientific collaboration networks. II. Shortest paths, weighted networks, and centralitv /7 Phvs. Rev. E 64, 016132. 2001.

36. Brandes U. On variants of shortest-path betweenness centralitv and their generic computation /7 Soe. Networks. 2008. V. 30. P. 136 145.

37. Jel classification system / EeonLit Subject Descriptors. 2016. [Electron, rcsourccl-https://www.acawcb.org/cconlit/jclCodcs.php7vicw jel.

38. Бредихин С. В., Ляпунов В. М., Щербакова Н. Г. Структура сети цитирования научных статей /7 Пробл. информ. 2016. № 3. С. 28 43.

Бредихин Сергей Все-

«володович канд. техн. наук, ведущий научный сотрудник Ин-та вычислительной математики и математической геофизики СО РАН; e-mail: bred nsc.ru;

Сергей Бредихин окончил механико-математический факультет Новосибирского государственного университета в 1968 г. С 1968 г. сотрудник Института автоматики и электрометрии СО РАН. Кандидат технических наук с 1983 i\ В период 1988 2017 гг. руководил лабораторией ИВМиМГ СО РАН. Исполнял обязанности тсхни чсского директора проекта „Сеть Интернет Новосибирских) научного центра". Лауреат государственной премии РФ

по науке и технике 2012 г. Сфера научных интересов: анализ и измерение распределенных информационных сетей. Автор и соавтор более ста научных работ и двух монографий: „Методы библиометрии и рынок электронной науч"

"

Sergey Bredikhin graduated from Novosibirsk State University in 1968, faculty of Mechanics and Mathematics, and became an employee of Institute of Automation and Electrometry SB RAS. In 1983 he received PhD degree in Engineering Science. Since 1988 2017 he was the head of the laboratory of Computing Center (now ICM&MG) SB RAS. He was the

technical manager of „Akademgorodok Internet "

and engineering RF at 2012. Sphere of his scientific interests analysis and measurement of the distributed information networks. He is the author and co-author of more than hundred scientific works and two monographs: „Metodv bibliometrii i rvnok electronnov nauchnov periodiki", „Analiz tsitirovaniva v bibliometrii".

Ляпунов Виктор Михайлович ведущий инженер Ин-та вычислительной математики и математической геофизики СО РАН; e-mail: vicOnsc. ru;

Виктор Ляпунов окончил механико-математический факультет Новосибирских) государственного университета в 1978 i'. В 1978 г. стал сотрудником Вычислительного центра СО АН СССР, а с 1990 i'. сотрудником Института систем информатики СО АН СССР. С 2004 г. ведущий инженер Института вычислительной математики и математической геофизики СО РАН. Занимается вопросами извлечения информации из баз данных и обработкой больших массивов данных. Соавтор более 10 работ в этой области.

Victor Lyapunov graduated from Novosibirsk State University in 1978 (faculty of Mechanics and Mathematics). In 1978, he became an employee of Computing Center of SB AS USSR, since 1990 an employee of Institute of Informatics Systems SB RAS. Since 2004 he works as software engineer in Institute of Computational Mathematics and Mathematical Geophysics SB RAS. His current research interests include methods of information extracting from databases and processing of large data sets. He is the co-author of more than 10 works in that area.

Щербакова Наталья Григорьевна

ст.

науч. сотр. Ин-та вычислительной математики

и математической геофизики СО РАН; e-mail: nataSnsc.ru.

Наталия Щербакова

окончила Новосибирский государственный университет но

специальности „ Математи че-"

1967 i'. работала в Институте математики СО РАН, затем в Институте автоматики и электрометрии СО РАН в области создания программного обеспечения систем передачи данных. С 2000 г. сотрудник Института вычислительной математики и математической геофизики СО РАН, где с 2002 г. занимает должность старшего научного сотрудника. Являлась участником проекта „Сеть Интернет Новосибирского научного "

анализа IP-сетей. Автор и соавтор более 40 работ, соавтор монографии „Анализ цитирования "

области исследования методов оценки научной деятельности на основе анализа цитирования научной литературы.

Natalia Shcherbakova graduated from Novosibirsk State University in 1967 (mathematical linguistics). Since 1967 she worked at Institute of Mathematics SB RAS, then at Institute of Automation and Electrometry SB RAS in the field of software design for data transmission systems. In 2000 the employee of Institute of Computational Mathematics and Mathematical Geophysics SB RAS, since 2002 works as senior researcher. She is a member of „Akademgorodok Internet Project", dealt with software of monitoring and the analysis of IP networks. She is the author and co-author of more than 40 works, the co-author of the monograph „Ansliz tsitirovaniva v bibliometrii". The current research interests lie in the field of bibliometrics: methods of measuring of scientific.

Дата поступления, 25.01.2011