[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Community finding in graphs
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] Community finding in graphs |
Date: |
Tue, 11 Dec 2007 18:12:46 +0100 |
Hi,
I just found an intriguing community detection algorithm that
tries to
reflect overlaps
A quick implementation in Python (and I assume it's similar in R):
# g is an undirected graph. If not, keep only the mutual edge pairs
before doing this
from igraph import *
# search for all cliques
cliques = [set(clique) for clique in g.cliques(min=3)]
# sort the cliques by length
cliques_by_length = {}
for clique in cliques:
k = len(clique)
if not cliques_by_length.has_key(k): cliques_by_length[k] = []
cliques_by_length[k].append(clique)
for k in cliques_by_length.keys():
# create clique adjacency graph for all k
adjacencies = []
cs = cliques_by_length[k]
for idx1, c1 in enumerate(cs):
for idx2, c2 in enumerate(cs):
if len(c1.union(c2)) == k+1:
adjacencies.append((idx1, idx2))
clique_graph = Graph(len(cs), adjacencies)
# determine the connected components
components = clique_graph.components()
print "k=%d:" % k
for component in components:
community = set()
for clique_idx in component: community.update(cs[clique_idx])
print " %s" % str(community)
This should work for small and medium sized sparse graphs. Note that
the clique detection routine in igraph uses substantially less memory
in the dev tree than in the last stable version, so you might consider
installing the development version.
--
T.
- [igraph] Community finding in graphs, Richard Geddes, 2007/12/10
- Re: [igraph] Community finding in graphs, Gabor Csardi, 2007/12/10
- Re: [igraph] Community finding in graphs, MATSUDA, Noriyuki, 2007/12/10
- Re: [igraph] Community finding in graphs, Gabor Csardi, 2007/12/11
- Re: [igraph] Community finding in graphs, Tamas Nepusz, 2007/12/11
- Re: [igraph] Community finding in graphs,
Tamas Nepusz <=
- Re: [igraph] Community finding in graphs, MATSUDA, Noriyuki, 2007/12/11
- Re: [igraph] Community finding in graphs, MATSUDA, Noriyuki, 2007/12/11