Теория графов: расчет коэффициента кластеризации

Question

Я провожу некоторые исследования и дошел до того, что вычислил коэффициент кластеризации графа.

Согласно этот документ напрямую связан с моими исследованиями :

Коэффициент кластеризации C (p) равен определяется следующим образом. Предположим, что вершина v имеет k _v соседей; тогда в большинство (k _v * (k _v -1)) / 2 ребра могут существуют между ними (это происходит, когда каждый сосед v связан с каждый сосед V). Пусть C _v обозначим долю этих допустимых края, которые на самом деле существуют. Определите C как среднее значение C _v по всем v

Но эта статья в Википедии на эту тему говорит по-другому :

C = (количество закрытых триплетов) / (количество подключенных триплетов)

Мне кажется, что последнее более вычислительно дорого.

Так что на самом деле мой вопрос: они эквивалентны?

Следует отметить, что статья цитируется в статье в Википедии.

Спасибо за ваше время.

Answer 1

Две формулы не совпадают; это два разных способа вычисления глобального коэффициента кластеризации.

Одним из способов является усреднение коэффициентов кластеризации (C_i [1]) всех узлов (это метод, который вы процитировали из Ватта и Строгатца). Однако в [2, p204] Ньюман утверждает, что этот метод менее предпочтителен, чем второй (тот, который вы получили из википедии). Он обосновывает это тем, что указывает, как в значении глобального коэффициента кластеризации могут доминировать узлы низкой степени из-за знаменателя C_i [1]. Таким образом, в сети с множеством узлов низких степеней вы в конечном итоге получите большое значение для глобального коэффициента кластеризации, которое, как утверждает Ньюман, было бы не представительным.

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

Две формулы разные и были предложены в разные моменты времени. Тот, который вы цитировали из «Уотта и Строгатца», старше, и, возможно, поэтому он, кажется, использовался чаще. Ньюман также объясняет, что две формулы далеки от 1008 * от эквивалента и не должны использоваться как таковые. Он говорит, что они могут дать существенно разные цифры для данной сети, однако не объясняет почему.

[1] C_i = (количество пар соседей из i , которые связаны) / (количество пар соседей из i )

[2] Ньюман, М.Е.Дж. Сети: введение. Оксфорд Нью-Йорк: издательство Оксфордского университета, 2010г. Печать.

Edit:

Я включаю здесь серию расчетов для того же случайного графа ER. Вы можете увидеть, как два метода дают разные результаты, даже для неориентированных графов. (сделано с использованием Mathematica)

Answer 2

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

sum_v lambda(v)/tau(v) = 3 x # triangles / # connected triples

, где lambda(v) - это число треугольников, содержащих v, а tau(v) - это число связанных троек, для которых v - средняя вершина,т.е. смежный с каждым из 2 других ребер.

Теперь каждый треугольник трижды подсчитывается в числителе LHS.Однако каждая связная тройка подсчитывается только один раз для средней вершины на LHS, поэтому знаменатели одинаковы.

Answer 3

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

  <-----
4 -----> 5
|<--||-->
|   ||
|-> 6  -> 7

4(IN [5,6], OUT [5,6])
5(IN [4,6], OUT [4])
6(IN [4], OUT [4,5,7])
7(IN [6], OUT [])

центральный = 6

localCC = 2/4 * 3 = 1/6

globalCC = 1/3

Answer 4

есть отличная страница для изучения основ!

http://www.learner.org/courses/mathilluminated/interactives/network/

все о кластерных коэффициентах, маленьком мире и так далее ...

Answer 5

Я бы не стал доверять этой статье в Википедии. Первая формула, которую вы цитировали, в настоящее время определяется как средний коэффициент кластеризации, поэтому она является средним значением всех локальных коэффициентов кластеризации для графика g . Это ни в коем случае не совпадает с глобальным коэффициентом кластеризации, как метко выразился xk_id.