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

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

Согласно этой статье, непосредственно связанной с моими исследованиями:

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

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

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

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

Итак, действительно мой вопрос: эквивалентны ли они?

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

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

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

[2] Newman, M.E.J. Networks: введение. Оксфорд Нью-Йорк: издательство Оксфордского университета, 2010. Печать.

Edit:

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

Ответ 3

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

  <-----
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 [])

central = 6

localCC = 2/4 * 3 = 1/6

globalCC = 1/3

Ответ 4

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