теория графов и modularity (Newman 2006)

[Анна]

Скажите пожалуйста, не сталкивался ли кто-то с таким понятием - modularity (Newman 2006, Ronhovde and Nussinov 2010)? к гисам это отношения не имеет правда, но решила попробовала спросить здесь - может кто-то случайно сталкивался? или сможет направить на ресурс, где спросить\почитать?

вопрос у меня такой:
при расчете modularity учитывается ли длина ветвей между узлами или нет? и вообще - не поможет ли кто-нибудь разобраться подетальнее в алгоритме?

пс. сразу извиняюсь, если вопрос глупый:)

[bim2010]

вопрос у меня такой: при расчете modularity учитывается ли длина ветвей между узлами или нет?

"Each community has a pointer to one of its neighbors - the one which would"
А как можно определить своих "соседей" не зная расстояния до них?
Один из входных параметров – graph, на мой взгляд, задается множеством вершин V и множеством ребер E между этими вершинами.

Let us assume that the eigenvalues are labeled in decreasing order, β1 ≥ β 2 ≥ … ≥ β n . We want to maximize the modularity by choosing an appropriate division of the network, or equivalently by choosing the value of the index vector s. This means choosing s so as to concentrate as much weight as possible in terms of the sum in Eq. 4 involving the largest (most positive) eigenvalues. If there were no other constraints on our choice of s (apart from normalization), this would be an easy task: we would simply chose s proportional to the eigenvector u 1. This places all of the weight in the term involving the largest eigenvalue β1, the other terms being automatically zero, because the eigenvectors are orthogonal.

Т.е. ребру присваивается вес. Тогда граф называется взвешенным. (частный случай - длина ветви графа)
Описание стр 132, (58,127)
Смотрим исходные тексты здесь
или здесь
igraph-0.5.5-msvc\igraph-0.5.5-msvc\src\fast_community.c
По Вашей второй ссылке Ronhovde and Nussinov 2010
я так и не смог получить текст статьи в PDF, хотя зарегистрировался и получил подтверждение на регистрацию.

Modularity(модулярность) - оценка качества разбиения графа на подграфы, насколько данное разбиение качественно, т.е. существует много ребер, лежащих внутри сообществ, и мало ребер, лежащих вне сообществ, соединяющих сообщества между собой. Применение алгоритма CNM (Clauset, Newman, Moore) обнаружения сообществ имеет смысл, если значение модулярности находится в диапазоне от 0.3 до 0.7, т.е. сеть имеет вполне различимую структуру с сообществами.

Ссылки по теме
igraph: Network analysis and visualization
Multi-Level Algorithms for Modularity Clustering
Optimal map of the modular structure of complex networks
Fast algorithm for detecting community structure in networks
Finding community structure in very large networks
http://arxiv.org/abs/cond-mat/0408187
Optimisation of Clustering Algorithms for the Identification of Customer Profiles from Shopping Cart Data
стр 52
Newman M E
Modularity and community structure in networks
http://www.ncbi.nlm.nih.gov/pubmed?term ... %22[Author]
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC14598/
Finding Community Structure in Megascale Social Networks

Community Detection In R
http://igraph.rubyforge.org/igraph/clas ... unity.html
http://intersci.ss.uci.edu/wiki/index.p ... _functions
http://brainarray.mbni.med.umich.edu/glay/
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2995124/
http://bioinformatics.oxfordjournals.or ... /3135.full
http://igraph.sourceforge.net/screenshots2.html

Алгоритмов по теме много. Для выбора надо знать больше о задаче.
Возможно что не один из перечисленных не подойдет.
Успеха!

[Анна]

bim, спасибо большое!!
я тоже смотрела igraph. Попробую расписать задачу с картинкой, чтобы было понятнее, и выложить, потому что все-таки пока несовсем мне ясно, модулярность - это то, что нужно или нет.

[Игорь Черниенко]

Попробуйте еще тут спросить http://molbiol.ru/forums/index.php?show ... 724&st=300
Форум аж сам Шипунов модерирует :о)

[bim2010]

Нашел вторую статью Local resolution limit free Potts model for community detection
Например, в этой работе Finding community structure in very large networks рассматриваются невзвешенные сети. Модулярность – как инструмент определения качества кластеризации описан в статье. Есть ли различия в формуле расчета модулярности для взвешенного или не взвешенного графа? Есть. Смотрим здесь
igraph-0.5.5-msvc\igraph-0.5.5-msvc\src\community.c
* Modularity on weighted graphs is also meaningful. When taking edge
* weights into account, `Aij' becomes the weight of the corresponding
* edge (or 0 if there is no edge), `ki' is the total weight of edges
* adjacent to vertex `i', `kj' is the total weight of edges adjacent
* to vertex `j' and `m' is the total weight of all edges.

Параметр weights ниже по тексту:

Код: Выделить всё

/**
 * \function igraph_modularity
 * \brief Calculate the modularity of a graph with respect to some vertex types
 * 
 * The modularity of a graph with respect to some division (or vertex
 * types) measures how good the division is, or how separated are the 
 * different vertex types from each other. It defined as 
 * Q=1/(2m) * sum(Aij-ki*kj/(2m)delta(ci,cj),i,j), here `m' is the
 * number of edges, `Aij' is the element of the `A' adjacency matrix
 * in row `i' and column `j', `ki' is the degree of `i', `kj' is the
 * degree of `j', `ci' is the type (or component) of `i', `cj' that of
 * `j', the sum goes over all `i' and `j' pairs of vertices, and
 * `delta(x,y)' is one if x=y and zero otherwise.
 *
 * </para><para>
 * Modularity on weighted graphs is also meaningful. When taking edge
 * weights into account, `Aij' becomes the weight of the corresponding
 * edge (or 0 if there is no edge), `ki' is the total weight of edges
 * adjacent to vertex `i', `kj' is the total weight of edges adjacent
 * to vertex `j' and `m' is the total weight of all edges.
 * 
 * </para><para>
 * See also MEJ Newman and M Girvan: Finding and evaluating community
 * structure in networks. Physical Review E 69 026113, 2004.
 * \param graph The input graph.
 * \param membership Numeric vector which gives the type of each
 *     vertex, ie. the component to which it belongs.
 * \param modularity Pointer to a real number, the result will be
 *     stored here.
 * \param weights Weight vector or NULL if no weights are specified.
 * \return Error code.
 * 
 * Time complexity: O(|V|+|E|), the number of vertices plus the number
 * of edges.
 */
int igraph_modularity(const igraph_t *graph, 
		      const igraph_vector_t *membership,
		      igraph_real_t *modularity,
			  const igraph_vector_t *weights) {
  
  igraph_vector_t e, a;
  long int types=igraph_vector_max(membership)+1;
  long int no_of_edges=igraph_ecount(graph);
  long int i;
  igraph_integer_t from, to, m;
  long int c1, c2;
  
  IGRAPH_VECTOR_INIT_FINALLY(&e, types);
  IGRAPH_VECTOR_INIT_FINALLY(&a, types);
  
  if (weights) {
    if (igraph_vector_size(weights) < no_of_edges)
      IGRAPH_ERROR("cannot calculate modularity, weight vector too short",
        IGRAPH_EINVAL);
    m=igraph_vector_sum(weights);
    for (i=0; i<no_of_edges; i++) {
      igraph_real_t w=VECTOR(*weights)[i];
      igraph_edge(graph, i, &from, &to);
      c1=VECTOR(*membership)[(long int)from];
      c2=VECTOR(*membership)[(long int)to];
      if (c1==c2) VECTOR(e)[c1] += 2*w;
      VECTOR(a)[c1] += w;
      VECTOR(a)[c2] += w;
    }
  } else {
    m=no_of_edges;
    for (i=0; i<no_of_edges; i++) {
      igraph_edge(graph, i, &from, &to);
      c1=VECTOR(*membership)[(long int)from];
      c2=VECTOR(*membership)[(long int)to];
      if (c1==c2) VECTOR(e)[c1] += 2;
      VECTOR(a)[c1] += 1;
      VECTOR(a)[c2] += 1;
    }
  }

  *modularity=0.0;
  for (i=0; i<types; i++) {
    igraph_real_t tmp=VECTOR(a)[i]/2/m;
    *modularity += VECTOR(e)[i]/2/m;
    *modularity -= tmp*tmp;
  }
  
  igraph_vector_destroy(&e);
  igraph_vector_destroy(&a);
  IGRAPH_FINALLY_CLEAN(2);
  
  return 0;
}

Существую ли другие критерии качества кластеризации...

[Анна]

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

Screen shot 2011-01-07 at 12.50.56.png (20.87 КБ) 15039 просмотров

Screen shot 2011-01-07 at 12.57.58.png (12.8 КБ) 15039 просмотров

[gamm]

на картинке 1 - граф (дерево), терминальные ветви окрашены по принадлежности к определенному классу (всего 5 классов в данном случае), мне нужно определить насколько случайным образом распределены классы (или наоброт - насколько они сгруппированы). Как это сделать?

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

Можно использовать дерево для определения расстояния между терминалами (по дереву), и использовать перестановочный тест Мантеля и ANOSIM (оба есть в R).

Тесты дают вероятность, можно проверять гипотезы.

[bim2010]

мне нужно определить насколько случайным образом распределены классы
(или наоброт - насколько они сгруппированы)

На мой взгляд, это разные понятия. Задача пока не ясна (не описана).
Еще методы кластерного анализа pvclust
silhouette cluster

[gamm]

мне нужно определить насколько случайным образом распределены классы
(или наоброт - насколько они сгруппированы)

На мой взгляд, это разные понятия. Задача пока не ясна (не описана).

но весьма напоминает классическую задачу в экологии/биологии/медицине: даны две классификации, установить зависит ли одна от другой (и если зависит, то насколько). Если бы не иерархия, то был бы обычный Хи-квадрат. Если бы было только расстояние между объектами, то получаем обычный тест Мантеля.

Расстояние между объектами есть, но не понятно, что делать с деревом - то ли расстояние на нем считать, то ли классы из него получать

[Анна]

спасибо bim и gamm

Если бы все было так просто (а именно хи-квадрат или Манель-тест), я бы не спрашивала)

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

[gamm]

спасибо bim и gamm
Еще раз попробую объяснить задачу: есть граф, постороенный по определенному алгоритму, на основе признаков никак не связанных с анализируемым - этот граф показывает степень родства между видами животных и длина ветвей дереве определяет возраст связи (чем длинее - тем дольше по времени). Есть признак - цвет в данном случае, но может быть любая категориальная переменная (например, тип местообитания - лес, луг, поле и т.п.). Каждый вид живет в своем местообитании, поэтому можно на терминальные ветви (узлы) нанести определенный тип местообитания (как представлено на картинке 1). Теперь вопрос - как оценить сгруппированны ли местообитания по степени родства видов или нет? есть ли тенденция у близкородственных видов (сгруппированных по дереву) жить в похожих условиях (показано цветом)?
то есть нужно понять "группировка по дереву" соотвествует ли "группировке" по местообитанию (и наоброт) с учетом длин ветвей.

что и предполагалось

то, что Вы описываете, и есть классическая задача, хотя вместо расстояния по дереву я чаще встречал расстояние в географическом пространстве. Посмотрите anosim(vegan) в R: ваши категориальные переменные - группировка, а расстояния по дереву - dissimilarity matrix.

Получите распределение, и положение статистики на нем, можно проверять гипотезы. Ничего большего, скорее всего, не получится, поскольку и филогенетическое дерево дает только вероятности, а не ответы (если взять ту же STRUCTURE, то там - МСМС).

[Анна]

спасибо gamm!
буду пробовать) но все же пока от модулярности не хочу отказываться тоже - уж очень привлекательно выглядит описание.

[gamm]

спасибо gamm!
буду пробовать) но все же пока от модулярности не хочу отказываться тоже - уж очень привлекательно выглядит описание.

колхоз - дело добровольное

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