Перекрытие обнаружения сообщества с помощью igraph или других библиотек

Question

Я хотел бы обнаружить перекрывающиеся сообщества в небольших сетях/графиках. Посредством перекрытия я имею в виду, что узел может быть включен в более чем одно сообщество/кластеры на выходе алгоритма обнаружения.

Я рассмотрел различные алгоритмы обнаружения сообщества, которые были предоставлены igraph, но я думаю, что ни одна из них не обрабатывает перекрывающиеся сообщества.

В идеале, я хотел бы иметь возможность программно использовать некоторую реализацию такого алгоритма (ов) в Python. Однако реализация на других языках тоже в порядке.

Answer 1

Я реализовал алгоритм Ahn et al a hierarchical link clustering некоторое время назад, используя интерфейс igraph на Python; см. его исходный код here.

Кроме того, внедрение CFinder в Python с использованием igraph довольно просто; это то, что я придумал:

#!/usr/bin/env python 
from itertools import combinations 

import igraph 
import optparse 

parser = optparse.OptionParser(usage="%prog [options] infile") 
parser.add_option("-k", metavar="K", default=3, type=int, 
     help="use a clique size of K") 

options, args = parser.parse_args() 

if not args: 
    parser.error("Required input file as first argument") 

k = options.k 
g = igraph.load(args[0], format="ncol", directed=False) 
cls = map(set, g.maximal_cliques(min=k)) 

edgelist = [] 
for i, j in combinations(range(len(cls)), 2): 
    if len(cls[i].intersection(cls[j])) >= k-1: 
     edgelist.append((i, j)) 

cg = igraph.Graph(edgelist, directed=False) 
clusters = cg.clusters() 
for cluster in clusters: 
    members = set() 
    for i in cluster: 
     members.update(cls[i]) 
    print "\t".join(g.vs[members]["name"]) 

Answer 2

Если вы не возражаете, используя другой язык программирования, у вас есть CFinder (Java), который основан на кликовым перколяции (она в основном ищет плотно соединенные клики), OSLOM (C++), которая оптимизирует статистическую меру, и конечно, другие.

В противном случае, если вы хотите придерживаться python, вы также можете применить метод к Evans & Lambiotte '09: 1) преобразовать граф в линейный граф, 2) применить на нем обычный метод обнаружения сообщества, например, используя igraph и 3) получить перекрывающиеся сообщества. Преобразование графика в линейный граф не выглядит слишком сложным и должно быть быстрым, если ваш исходный граф не слишком велик. В любом случае это будет быстрее, чем самообследование сообщества.

Примечания есть альтернативные методы в том, что Эванс & Lambiotte, чтобы получить перекрытие общин от обычного метода (взаимоисключающих сообществ), таких как те Bennet et al. '12 или Wang et al. '09. Однако их реализация кажется менее очевидной.

Answer 3

Согласно этому blog, NetworkX теперь можно вычислить для перекрытия сообществ.

Код, приведенный ниже, относится к методу перколяции клики и доступен в Networkx 11.6. Github here

import networkx as nx 
from itertools import combinations 

def get_percolated_cliques(G, k): 
perc_graph = nx.Graph() 
cliques = list(frozenset(c) for c in nx.find_cliques(G) if len(c) >= k) 
perc_graph.add_nodes_from(cliques) 

# Add an edge in the clique graph for each pair of cliques that percolate 
for c1, c2 in combinations(cliques, 2): 
    if len(c1.intersection(c2)) >= (k - 1): 
     perc_graph.add_edge(c1, c2) 

for component in nx.connected_components(perc_graph): 
    yield(frozenset.union(*component)) 

Answer 4

CFinder реализации Clique Percolation Method (CPM). Если вы используете python, Networkx уже реализует то же самое (see this link).

>>> G = nx.complete_graph(5) 
>>> K5 = nx.convert_node_labels_to_integers(G,first_label=2) 
>>> G.add_edges_from(K5.edges()) 
>>> c = list(nx.k_clique_communities(G, 4)) 
>>> list(c[0]) 
[0, 1, 2, 3, 4, 5, 6] 
>>> list(nx.k_clique_communities(G, 6))