Commits

Luke Cyca  committed da7ed2d

Created an installable package suitable for PyPI

  • Participants
  • Parent commits bb73de3

Comments (0)

Files changed (17)

File Makefile

-# Makefile for Sphinx documentation
-#
-
-EXEC= html
-
-
-# You can set these variables from the command line.
-SPHINXOPTS    =
-SPHINXBUILD   = sphinx-build
-PAPER         =
-BUILDDIR      = _build
-
-# Internal variables.
-PAPEROPT_a4     = -D latex_paper_size=a4
-PAPEROPT_letter = -D latex_paper_size=letter
-ALLSPHINXOPTS   = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) .
-
-.PHONY: help clean html dirhtml pickle json htmlhelp qthelp latex changes linkcheck doctest
-
-all: $(EXEC)
-	
-#########################################
-# Generic rules
-##########################################
-
-
-clean:
-	-rm -rf $(BUILDDIR)/*
-
-help:
-	@echo "Please use \`make <target>' where <target> is one of"
-	@echo "  html      to make standalone HTML files"
-	@echo "  dirhtml   to make HTML files named index.html in directories"
-	@echo "  pickle    to make pickle files"
-	@echo "  json      to make JSON files"
-	@echo "  htmlhelp  to make HTML files and a HTML help project"
-	@echo "  qthelp    to make HTML files and a qthelp project"
-	@echo "  latex     to make LaTeX files, you can set PAPER=a4 or PAPER=letter"
-	@echo "  changes   to make an overview of all changed/added/deprecated items"
-	@echo "  linkcheck to check all external links for integrity"
-	@echo "  doctest   to run all doctests embedded in the documentation (if enabled)"
-
-
-html:
-	$(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html
-	@echo
-	@echo "Build finished. The HTML pages are in $(BUILDDIR)/html."
-
-dirhtml:
-	$(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml
-	@echo
-	@echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml."
-
-pickle:
-	$(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle
-	@echo
-	@echo "Build finished; now you can process the pickle files."
-
-json:
-	$(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json
-	@echo
-	@echo "Build finished; now you can process the JSON files."
-
-htmlhelp:
-	$(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp
-	@echo
-	@echo "Build finished; now you can run HTML Help Workshop with the" \
-	      ".hhp project file in $(BUILDDIR)/htmlhelp."
-
-qthelp:
-	$(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp
-	@echo
-	@echo "Build finished; now you can run "qcollectiongenerator" with the" \
-	      ".qhcp project file in $(BUILDDIR)/qthelp, like this:"
-	@echo "# qcollectiongenerator $(BUILDDIR)/qthelp/CommunitydetectionforNetworkX.qhcp"
-	@echo "To view the help file:"
-	@echo "# assistant -collectionFile $(BUILDDIR)/qthelp/CommunitydetectionforNetworkX.qhc"
-
-latex:
-	$(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
-	@echo
-	@echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex."
-	@echo "Run \`make all-pdf' or \`make all-ps' in that directory to" \
-	      "run these through (pdf)latex."
-
-changes:
-	$(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes
-	@echo
-	@echo "The overview file is in $(BUILDDIR)/changes."
-
-linkcheck:
-	$(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck
-	@echo
-	@echo "Link check complete; look for any errors in the above output " \
-	      "or in $(BUILDDIR)/linkcheck/output.txt."
-
-doctest:
-	$(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest
-	@echo "Testing of doctests in the sources finished, look at the " \
-	      "results in $(BUILDDIR)/doctest/output.txt."
+Louvain Community Detection
+===========================
+
+Installing
+----------
+
+To build and install run::
+
+     python setup.py install
+
+Usage
+-----
+
+To use from the command line::
+
+     $ community <filename>
+
+filename is a binary file as generated by the
+convert utility distributed with the C implementation
+
+To use as a python library::
+
+     import community
+
+Documentation
+-------------
+
+To generate documentation run::
+
+     pip install numpydoc sphinx
+     cd docs
+     make
+
+Tests
+-----
+
+To run tests::
+
+     pip install nose
+     python setup.py test

File _static/default.css

-/**
- * Alternate Sphinx design
- * Originally created by Armin Ronacher for Werkzeug, adapted by Georg Brandl.
- */
-
-body {
-    font-family: 'Lucida Grande', 'Lucida Sans Unicode', 'Geneva', 'Verdana', sans-serif;
-    font-size: 14px;
-    letter-spacing: -0.01em;
-    line-height: 150%;
-    text-align: center;
-    /*background-color: #AFC1C4; */
-    background-color: #BFD1D4;
-    color: black;
-    padding: 0;
-    border: 1px solid #aaa;
-
-    margin: 0px 80px 0px 80px;
-    min-width: 740px;
-}
-
-a {
-    color: #CA7900;
-    text-decoration: none;
-}
-
-a:hover {
-    color: #2491CF;
-}
-
-pre {
-    font-family: 'Consolas', 'Deja Vu Sans Mono', 'Bitstream Vera Sans Mono', monospace;
-    font-size: 0.95em;
-    letter-spacing: 0.015em;
-    padding: 0.5em;
-    border: 1px solid #ccc;
-    background-color: #f8f8f8;
-}
-
-td.linenos pre {
-    padding: 0.5em 0;
-    border: 0;
-    background-color: transparent;
-    color: #aaa;
-}
-
-table.highlighttable {
-    margin-left: 0.5em;
-}
-
-table.highlighttable td {
-    padding: 0 0.5em 0 0.5em;
-}
-
-cite, code, tt {
-    font-family: 'Consolas', 'Deja Vu Sans Mono', 'Bitstream Vera Sans Mono', monospace;
-    font-size: 0.95em;
-    letter-spacing: 0.01em;
-}
-
-hr {
-    border: 1px solid #abc;
-    margin: 2em;
-}
-
-tt {
-    background-color: #f2f2f2;
-    border-bottom: 1px solid #ddd;
-    color: #333;
-}
-
-tt.descname {
-    background-color: transparent;
-    font-weight: bold;
-    font-size: 1.2em;
-    border: 0;
-}
-
-tt.descclassname {
-    background-color: transparent;
-    border: 0;
-}
-
-tt.xref {
-    background-color: transparent;
-    font-weight: bold;
-    border: 0;
-}
-
-a tt {
-    background-color: transparent;
-    font-weight: bold;
-    border: 0;
-    color: #CA7900;
-}
-
-a tt:hover {
-    color: #2491CF;
-}
-
-dl {
-    margin-bottom: 15px;
-}
-
-dd p {
-    margin-top: 0px;
-}
-
-dd ul, dd table {
-    margin-bottom: 10px;
-}
-
-dd {
-    margin-top: 3px;
-    margin-bottom: 10px;
-    margin-left: 30px;
-}
-
-.refcount {
-    color: #060;
-}
-
-dt:target,
-.highlight {
-    background-color: #fbe54e;
-}
-
-dl.class, dl.function {
-    border-top: 2px solid #888;
-}
-
-dl.method, dl.attribute {
-    border-top: 1px solid #aaa;
-}
-
-dl.glossary dt {
-    font-weight: bold;
-    font-size: 1.1em;
-}
-
-pre {
-    line-height: 120%;
-}
-
-pre a {
-    color: inherit;
-    text-decoration: underline;
-}
-
-.first {
-    margin-top: 0 !important;
-}
-
-div.document {
-    background-color: white;
-    text-align: left;
-    background-image: url(contents.png);
-    background-repeat: repeat-x;
-}
-
-/*
-div.documentwrapper {
-    width: 100%;
-}
-*/
-
-div.clearer {
-    clear: both;
-}
-
-div.related h3 {
-    display: none;
-}
-
-div.related ul {
-    background-image: url(navigation.png);
-    height: 2em;
-    list-style: none;
-    border-top: 1px solid #ddd;
-    border-bottom: 1px solid #ddd;
-    margin: 0;
-    padding-left: 10px;
-}
-
-div.related ul li {
-    margin: 0;
-    padding: 0;
-    height: 2em;
-    float: left;
-}
-
-div.related ul li.right {
-    float: right;
-    margin-right: 5px;
-}
-
-div.related ul li a {
-    margin: 0;
-    padding: 0 5px 0 5px;
-    line-height: 1.75em;
-    color: #EE9816;
-}
-
-div.related ul li a:hover {
-    color: #3CA8E7;
-}
-
-div.body {
-    margin: 0;
-    padding: 0.5em 20px 20px 20px;
-}
-
-div.bodywrapper {
-    margin: 0 240px 0 0;
-    border-right: 1px solid #ccc;
-}
-
-div.body a {
-    text-decoration: underline;
-}
-
-div.sphinxsidebar {
-    margin: 0;
-    padding: 0.5em 15px 15px 0;
-    width: 210px;
-    float: right;
-    text-align: left;
-/*    margin-left: -100%; */
-}
-
-div.sphinxsidebar h4, div.sphinxsidebar h3 {
-    margin: 1em 0 0.5em 0;
-    font-size: 0.9em;
-    padding: 0.1em 0 0.1em 0.5em;
-    color: white;
-    border: 1px solid #86989B;
-    background-color: #AFC1C4;
-}
-
-div.sphinxsidebar ul {
-    padding-left: 1.5em;
-    margin-top: 7px;
-    list-style: none;
-    padding: 0;
-    line-height: 130%;
-}
-
-div.sphinxsidebar ul ul {
-    list-style: square;
-    margin-left: 20px;
-}
-
-p {
-    margin: 0.8em 0 0.5em 0;
-}
-
-p.rubric {
-    font-weight: bold;
-}
-
-h1 {
-    margin: 0;
-    padding: 0.7em 0 0.3em 0;
-    font-size: 1.5em;
-    color: #11557C;
-}
-
-h2 {
-    margin: 1.3em 0 0.2em 0;
-    font-size: 1.35em;
-    padding: 0;
-}
-
-h3 {
-    margin: 1em 0 -0.3em 0;
-    font-size: 1.2em;
-}
-
-h1 a, h2 a, h3 a, h4 a, h5 a, h6 a {
-    color: black!important;
-}
-
-h1 a.anchor, h2 a.anchor, h3 a.anchor, h4 a.anchor, h5 a.anchor, h6 a.anchor {
-    display: none;
-    margin: 0 0 0 0.3em;
-    padding: 0 0.2em 0 0.2em;
-    color: #aaa!important;
-}
-
-h1:hover a.anchor, h2:hover a.anchor, h3:hover a.anchor, h4:hover a.anchor,
-h5:hover a.anchor, h6:hover a.anchor {
-    display: inline;
-}
-
-h1 a.anchor:hover, h2 a.anchor:hover, h3 a.anchor:hover, h4 a.anchor:hover,
-h5 a.anchor:hover, h6 a.anchor:hover {
-    color: #777;
-    background-color: #eee;
-}
-
-table {
-    border-collapse: collapse;
-    margin: 0 -0.5em 0 -0.5em;
-}
-
-table td, table th {
-    padding: 0.2em 0.5em 0.2em 0.5em;
-}
-
-div.footer {
-    background-color: #E3EFF1;
-    color: #86989B;
-    padding: 3px 8px 3px 0;
-    clear: both;
-    font-size: 0.8em;
-    text-align: right;
-}
-
-div.footer a {
-    color: #86989B;
-    text-decoration: underline;
-}
-
-div.pagination {
-    margin-top: 2em;
-    padding-top: 0.5em;
-    border-top: 1px solid black;
-    text-align: center;
-}
-
-div.sphinxsidebar ul.toc {
-    margin: 1em 0 1em 0;
-    padding: 0 0 0 0.5em;
-    list-style: none;
-}
-
-div.sphinxsidebar ul.toc li {
-    margin: 0.5em 0 0.5em 0;
-    font-size: 0.9em;
-    line-height: 130%;
-}
-
-div.sphinxsidebar ul.toc li p {
-    margin: 0;
-    padding: 0;
-}
-
-div.sphinxsidebar ul.toc ul {
-    margin: 0.2em 0 0.2em 0;
-    padding: 0 0 0 1.8em;
-}
-
-div.sphinxsidebar ul.toc ul li {
-    padding: 0;
-}
-
-div.admonition, div.warning {
-    font-size: 0.9em;
-    margin: 1em 0 0 0;
-    border: 1px solid #86989B;
-    background-color: #f7f7f7;
-}
-
-div.admonition p, div.warning p {
-    margin: 0.5em 1em 0.5em 1em;
-    padding: 0;
-}
-
-div.admonition pre, div.warning pre {
-    margin: 0.4em 1em 0.4em 1em;
-}
-
-div.admonition p.admonition-title,
-div.warning p.admonition-title {
-    margin: 0;
-    padding: 0.1em 0 0.1em 0.5em;
-    color: white;
-    border-bottom: 1px solid #86989B;
-    font-weight: bold;
-    background-color: #AFC1C4;
-}
-
-div.warning {
-    border: 1px solid #940000;
-}
-
-div.warning p.admonition-title {
-    background-color: #CF0000;
-    border-bottom-color: #940000;
-}
-
-div.admonition ul, div.admonition ol,
-div.warning ul, div.warning ol {
-    margin: 0.1em 0.5em 0.5em 3em;
-    padding: 0;
-}
-
-div.versioninfo {
-    margin: 1em 0 0 0;
-    border: 1px solid #ccc;
-    background-color: #DDEAF0;
-    padding: 8px;
-    line-height: 1.3em;
-    font-size: 0.9em;
-}
-
-
-a.headerlink {
-    color: #c60f0f!important;
-    font-size: 1em;
-    margin-left: 6px;
-    padding: 0 4px 0 4px;
-    text-decoration: none!important;
-    visibility: hidden;
-}
-
-h1:hover > a.headerlink,
-h2:hover > a.headerlink,
-h3:hover > a.headerlink,
-h4:hover > a.headerlink,
-h5:hover > a.headerlink,
-h6:hover > a.headerlink,
-dt:hover > a.headerlink {
-    visibility: visible;
-}
-
-a.headerlink:hover {
-    background-color: #ccc;
-    color: white!important;
-}
-
-table.indextable td {
-    text-align: left;
-    vertical-align: top;
-}
-
-table.indextable dl, table.indextable dd {
-    margin-top: 0;
-    margin-bottom: 0;
-}
-
-table.indextable tr.pcap {
-    height: 10px;
-}
-
-table.indextable tr.cap {
-    margin-top: 10px;
-    background-color: #f2f2f2;
-}
-
-img.toggler {
-    margin-right: 3px;
-    margin-top: 3px;
-    cursor: pointer;
-}
-
-img.inheritance {
-    border: 0px
-}
-
-form.pfform {
-    margin: 10px 0 20px 0;
-}
-
-table.contentstable {
-    width: 90%;
-}
-
-table.contentstable p.biglink {
-    line-height: 150%;
-}
-
-a.biglink {
-    font-size: 1.3em;
-}
-
-span.linkdescr {
-    font-style: italic;
-    padding-top: 5px;
-    font-size: 90%;
-}
-
-ul.search {
-    margin: 10px 0 0 20px;
-    padding: 0;
-}
-
-ul.search li {
-    padding: 5px 0 5px 20px;
-    background-image: url(file.png);
-    background-repeat: no-repeat;
-    background-position: 0 7px;
-}
-
-ul.search li a {
-    font-weight: bold;
-}
-
-ul.search li div.context {
-    color: #888;
-    margin: 2px 0 0 30px;
-    text-align: left;
-}
-
-ul.keywordmatches li.goodmatch a {
-    font-weight: bold;
-}

File _templates/layout.html

-{% extends "!layout.html" %}
-
-
-{% block rootrellink %}
-        <li><a href="{{ pathto('index') }}">home</a>|&nbsp;</li>
-        <li><a href="{{ pathto('search') }}">search</a>|&nbsp;</li>
-       <li><a href="{{ pathto('api') }}">documentation </a> &raquo;</li>
-{% endblock %}
-
-{%- block extrahead %}
-{{ super() }}
-<script type="text/javascript">
-var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
-document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
-</script>
-<script type="text/javascript">
-try{ 
-var pageTracker = _gat._getTracker("UA-7251741-1");
-pageTracker._trackPageview();
-} catch(err) {} 
-</script>
-{% endblock %}
-
-{% block footer %}
-{{ super() }}
-<div class="footer">This page uses <a href="http://analytics.google.com/">
-Google Analytics</a> to collect statistics. You can disable it by blocking
-the JavaScript coming from www.google-analytics.com.
-<script type="text/javascript">
-  (function() {
-    var ga = document.createElement('script');
-    ga.src = ('https:' == document.location.protocol ?
-              'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
-    ga.setAttribute('async', 'true');
-    document.documentElement.firstChild.appendChild(ga);
-  })();
-</script>
-</div>
-{% endblock %}
-
-{% block relbar1 %}
-
-<div style="background-color: white; text-align: left; padding: 10px 10px 15px 15px">
-<a href="{{ pathto('index') }}">Community detection</a>
-</div>
-{{ super() }}
-{% endblock %}
-
-{# put the sidebar before the body #}
-{% block sidebar1 %}{{ sidebar() }}{% endblock %}
-{% block sidebar2 %}{% endblock %}

File api.rst

-community API
-=============
-
-.. toctree::
-   :maxdepth: 2
-
-
-.. automodule:: community
-   :members:
-
-Indices and tables
-==================
-
-* :ref:`genindex`
-* :ref:`modindex`
-* :ref:`search`

File community.py

-#!/usr/bin/python
-# -*- coding: utf-8 -*-
-"""
-This module implements community detection.
-"""
-__all__ = ["partition_at_level", "modularity", "best_partition", "generate_dendogram", "induced_graph"]
-__author__ = """Thomas Aynaud (thomas.aynaud@lip6.fr)"""
-#    Copyright (C) 2009 by
-#    Thomas Aynaud <thomas.aynaud@lip6.fr>
-#    All rights reserved.
-#    BSD license.
-
-__PASS_MAX = -1
-__MIN = 0.0000001
-
-import networkx as nx
-import sys
-import types
-import array
-
-
-def partition_at_level(dendogram, level) :
-    """Return the partition of the nodes at the given level
-
-    A dendogram is a tree and each level is a partition of the graph nodes.
-    Level 0 is the first partition, which contains the smallest communities, and the best is len(dendogram) - 1.
-    The higher the level is, the bigger are the communities
-
-    Parameters
-    ----------
-    dendogram : list of dict
-       a list of partitions, ie dictionnaries where keys of the i+1 are the values of the i.
-    level : int
-       the level which belongs to [0..len(dendogram)-1]
-
-    Returns
-    -------
-    partition : dictionnary
-       A dictionary where keys are the nodes and the values are the set it belongs to
-
-    Raises
-    ------
-    KeyError
-       If the dendogram is not well formed or the level is too high
-
-    See Also
-    --------
-    best_partition which directly combines partition_at_level and generate_dendogram to obtain the partition of highest modularity
-
-    Examples
-    --------
-    >>> G=nx.erdos_renyi_graph(100, 0.01)
-    >>> dendo = generate_dendogram(G)
-    >>> for level in range(len(dendo) - 1) :
-    >>>     print "partition at level", level, "is", partition_at_level(dendo, level)
-    """
-    partition = dendogram[0].copy()
-    for index in range(1, level + 1) :
-        for node, community in partition.iteritems() :
-            partition[node] = dendogram[index][community]
-    return partition
-    
-
-def modularity(partition, graph) :
-    """Compute the modularity of a partition of a graph
-
-    Parameters
-    ----------
-    partition : dict
-       the partition of the nodes, i.e a dictionary where keys are their nodes and values the communities
-    graph : networkx.Graph
-       the networkx graph which is decomposed
-
-    Returns
-    -------
-    modularity : float
-       The modularity
-
-    Raises
-    ------
-    KeyError
-       If the partition is not a partition of all graph nodes
-    ValueError
-        If the graph has no link
-    TypeError
-        If graph is not a networkx.Graph
-
-    References
-    ----------
-    .. 1. Newman, M.E.J. & Girvan, M. Finding and evaluating community structure in networks. Physical Review E 69, 26113(2004).
-
-    Examples
-    --------
-    >>> G=nx.erdos_renyi_graph(100, 0.01)
-    >>> part = best_partition(G)
-    >>> modularity(part, G)
-    """
-    if type(graph) != nx.Graph :
-        raise TypeError("Bad graph type, use only non directed graph")
-
-    inc = dict([])
-    deg = dict([])
-    links = graph.size(weight='weight')
-    if links == 0 :
-        raise ValueError("A graph without link has an undefined modularity")
-    
-    for node in graph :
-        com = partition[node]
-        deg[com] = deg.get(com, 0.) + graph.degree(node, weight = 'weight')
-        for neighbor, datas in graph[node].iteritems() :
-            weight = datas.get("weight", 1)
-            if partition[neighbor] == com :
-                if neighbor == node :
-                    inc[com] = inc.get(com, 0.) + float(weight)
-                else :
-                    inc[com] = inc.get(com, 0.) + float(weight) / 2.
-
-    res = 0.
-    for com in set(partition.values()) :
-        res += (inc.get(com, 0.) / links) - (deg.get(com, 0.) / (2.*links))**2
-    return res
-
-
-def best_partition(graph, partition = None) :
-    """Compute the partition of the graph nodes which maximises the modularity
-    (or try..) using the Louvain heuristices
-
-    This is the partition of highest modularity, i.e. the highest partition of the dendogram
-    generated by the Louvain algorithm.
-    
-    Parameters
-    ----------
-    graph : networkx.Graph
-       the networkx graph which is decomposed
-    partition : dict, optionnal
-       the algorithm will start using this partition of the nodes. It's a dictionary where keys are their nodes and values the communities
-
-    Returns
-    -------
-    partition : dictionnary
-       The partition, with communities numbered from 0 to number of communities
-
-    Raises
-    ------
-    NetworkXError
-       If the graph is not Eulerian.
-
-    See Also
-    --------
-    generate_dendogram to obtain all the decompositions levels
-
-    Notes
-    -----
-    Uses Louvain algorithm
-
-    References
-    ----------
-    .. 1. Blondel, V.D. et al. Fast unfolding of communities in large networks. J. Stat. Mech 10008, 1-12(2008).
-
-    Examples
-    --------
-    >>>  #Basic usage
-    >>> G=nx.erdos_renyi_graph(100, 0.01)
-    >>> part = best_partition(G)
-    
-    >>> #other example to display a graph with its community :
-    >>> #better with karate_graph() as defined in networkx examples
-    >>> #erdos renyi don't have true community structure
-    >>> G = nx.erdos_renyi_graph(30, 0.05)
-    >>> #first compute the best partition
-    >>> partition = community.best_partition(G)
-    >>>  #drawing
-    >>> size = float(len(set(partition.values())))
-    >>> pos = nx.spring_layout(G)
-    >>> count = 0.
-    >>> for com in set(partition.values()) :
-    >>>     count = count + 1.
-    >>>     list_nodes = [nodes for nodes in partition.keys()
-    >>>                                 if partition[nodes] == com]
-    >>>     nx.draw_networkx_nodes(G, pos, list_nodes, node_size = 20,
-                                    node_color = str(count / size))
-    >>> nx.draw_networkx_edges(G,pos, alpha=0.5)
-    >>> plt.show()
-    """
-    dendo = generate_dendogram(graph, partition)
-    return partition_at_level(dendo, len(dendo) - 1 )
-
-
-def generate_dendogram(graph, part_init = None) :
-    """Find communities in the graph and return the associated dendogram
-
-    A dendogram is a tree and each level is a partition of the graph nodes.  Level 0 is the first partition, which contains the smallest communities, and the best is len(dendogram) - 1. The higher the level is, the bigger are the communities
-
-
-    Parameters
-    ----------
-    graph : networkx.Graph
-        the networkx graph which will be decomposed
-    part_init : dict, optionnal
-        the algorithm will start using this partition of the nodes. It's a dictionary where keys are their nodes and values the communities
-
-    Returns
-    -------
-    dendogram : list of dictionaries
-        a list of partitions, ie dictionnaries where keys of the i+1 are the values of the i. and where keys of the first are the nodes of graph
-    
-    Raises
-    ------
-    TypeError
-        If the graph is not a networkx.Graph
-
-    See Also
-    --------
-    best_partition
-
-    Notes
-    -----
-    Uses Louvain algorithm
-
-    References
-    ----------
-    .. 1. Blondel, V.D. et al. Fast unfolding of communities in large networks. J. Stat. Mech 10008, 1-12(2008).
-
-    Examples
-    --------
-    >>> G=nx.erdos_renyi_graph(100, 0.01)
-    >>> dendo = generate_dendogram(G)
-    >>> for level in range(len(dendo) - 1) :
-    >>>     print "partition at level", level, "is", partition_at_level(dendo, level)
-    """
-    if type(graph) != nx.Graph :
-        raise TypeError("Bad graph type, use only non directed graph")
-
-    #special case, when there is no link 
-    #the best partition is everyone in its community
-    if graph.number_of_edges() == 0 :
-        part = dict([])
-        for node in graph.nodes() :
-            part[node] = node
-        return part
-        
-    current_graph = graph.copy()
-    status = Status()
-    status.init(current_graph, part_init)
-    mod = __modularity(status)
-    status_list = list()
-    __one_level(current_graph, status)
-    new_mod = __modularity(status)
-    partition = __renumber(status.node2com)
-    status_list.append(partition)
-    mod = new_mod
-    current_graph = induced_graph(partition, current_graph)
-    status.init(current_graph)
-    
-    while True :
-        __one_level(current_graph, status)
-        new_mod = __modularity(status)
-        if new_mod - mod < __MIN :
-            break
-        partition = __renumber(status.node2com)
-        status_list.append(partition)
-        mod = new_mod
-        current_graph = induced_graph(partition, current_graph)
-        status.init(current_graph)
-    return status_list[:]
-
-
-def induced_graph(partition, graph) :
-    """Produce the graph where nodes are the communities
-
-    there is a link of weight w between communities if the sum of the weights of the links between their elements is w
-
-    Parameters
-    ----------
-    partition : dict
-       a dictionary where keys are graph nodes and  values the part the node belongs to
-    graph : networkx.Graph
-        the initial graph
-
-    Returns
-    -------
-    g : networkx.Graph
-       a networkx graph where nodes are the parts
-
-    Examples
-    --------
-    >>> n = 5
-    >>> g = nx.complete_graph(2*n)
-    >>> part = dict([])
-    >>> for node in g.nodes() :
-    >>>     part[node] = node % 2
-    >>> ind = induced_graph(part, g)
-    >>> goal = nx.Graph()
-    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])
-    >>> nx.is_isomorphic(int, goal)
-    True
-    """
-    ret = nx.Graph()
-    ret.add_nodes_from(partition.values())
-    
-    for node1, node2, datas in graph.edges_iter(data = True) :
-        weight = datas.get("weight", 1)
-        com1 = partition[node1]
-        com2 = partition[node2]
-        w_prec = ret.get_edge_data(com1, com2, {"weight":0}).get("weight", 1)
-        ret.add_edge(com1, com2, weight = w_prec + weight)
-        
-    return ret
-
-
-def __renumber(dictionary) :
-    """Renumber the values of the dictionary from 0 to n
-    """
-    count = 0
-    ret = dictionary.copy()
-    new_values = dict([])
-    
-    for key in dictionary.keys() :
-        value = dictionary[key]
-        new_value = new_values.get(value, -1)
-        if new_value == -1 :
-            new_values[value] = count
-            new_value = count
-            count = count + 1
-        ret[key] = new_value
-        
-    return ret
-
-
-def __load_binary(data) :
-    """Load binary graph as used by the cpp implementation of this algorithm
-    """
-    if type(data) == types.StringType :
-        data = open(data, "rb")
-        
-    reader = array.array("I")
-    reader.fromfile(data, 1)
-    num_nodes = reader.pop()
-    reader = array.array("I")
-    reader.fromfile(data, num_nodes)
-    cum_deg = reader.tolist()
-    num_links = reader.pop()
-    reader = array.array("I")
-    reader.fromfile(data, num_links)
-    links = reader.tolist()
-    graph = nx.Graph()
-    graph.add_nodes_from(range(num_nodes))
-    prec_deg = 0
-    
-    for index in range(num_nodes) :
-        last_deg = cum_deg[index]
-        neighbors = links[prec_deg:last_deg]
-        graph.add_edges_from([(index, int(neigh)) for neigh in neighbors])
-        prec_deg = last_deg
-        
-    return graph
-
-
-def __one_level(graph, status) :
-    """Compute one level of communities
-    """
-    modif = True
-    nb_pass_done = 0
-    cur_mod = __modularity(status)
-    new_mod = cur_mod
-    
-    while modif  and nb_pass_done != __PASS_MAX :
-        cur_mod = new_mod
-        modif = False
-        nb_pass_done += 1
-        
-        for node in graph.nodes() :
-            com_node = status.node2com[node]
-            degc_totw = status.gdegrees.get(node, 0.) / (status.total_weight*2.)
-            neigh_communities = __neighcom(node, graph, status)
-            __remove(node, com_node,
-                    neigh_communities.get(com_node, 0.), status)
-            best_com = com_node
-            best_increase = 0
-            for com, dnc in neigh_communities.iteritems() :
-                incr =  dnc  - status.degrees.get(com, 0.) * degc_totw
-                if incr > best_increase :
-                    best_increase = incr
-                    best_com = com                    
-            __insert(node, best_com,
-                    neigh_communities.get(best_com, 0.), status)
-            if best_com != com_node :
-                modif = True                
-        new_mod = __modularity(status)
-        if new_mod - cur_mod < __MIN :
-            break
-
-
-class Status :
-    """
-    To handle several data in one struct.
-
-    Could be replaced by named tuple, but don't want to depend on python 2.6
-    """
-    node2com = {}
-    total_weight = 0
-    internals = {}
-    degrees = {}
-    gdegrees = {}
-    
-    def __init__(self) :
-        self.node2com = dict([])
-        self.total_weight = 0
-        self.degrees = dict([])
-        self.gdegrees = dict([])
-        self.internals = dict([])
-        self.loops = dict([])
-        
-    def __str__(self) :
-        return ("node2com : " + str(self.node2com) + " degrees : "
-            + str(self.degrees) + " internals : " + str(self.internals)
-            + " total_weight : " + str(self.total_weight))
-
-    def copy(self) :
-        """Perform a deep copy of status"""
-        new_status = Status()
-        new_status.node2com = self.node2com.copy()
-        new_status.internals = self.internals.copy()
-        new_status.degrees = self.degrees.copy()
-        new_status.gdegrees = self.gdegrees.copy()
-        new_status.total_weight = self.total_weight
-
-    def init(self, graph, part = None) :
-        """Initialize the status of a graph with every node in one community"""
-        count = 0
-        self.node2com = dict([])
-        self.total_weight = 0
-        self.degrees = dict([])
-        self.gdegrees = dict([])
-        self.internals = dict([])
-        self.total_weight = graph.size(weight = 'weight')
-        if part == None :
-            for node in graph.nodes() :
-                self.node2com[node] = count
-                deg = float(graph.degree(node, weight = 'weight'))
-                if deg < 0 :
-                    raise ValueError("Bad graph type, use positive weights")
-                self.degrees[count] = deg
-                self.gdegrees[node] = deg
-                self.loops[node] = float(graph.get_edge_data(node, node,
-                                                 {"weight":0}).get("weight", 1))
-                self.internals[count] = self.loops[node]
-                count = count + 1
-        else :
-            for node in graph.nodes() :
-                com = part[node]
-                self.node2com[node] = com
-                deg = float(graph.degree(node, weigh = 'weight'))
-                self.degrees[com] = self.degrees.get(com, 0) + deg
-                self.gdegrees[node] = deg
-                inc = 0.
-                for neighbor, datas in graph[node].iteritems() :
-                    weight = datas.get("weight", 1)
-                    if weight <= 0 :
-                        raise ValueError("Bad graph type, use positive weights")
-                    if part[neighbor] == com :
-                        if neighbor == node :
-                            inc += float(weight)
-                        else :
-                            inc += float(weight) / 2.
-                self.internals[com] = self.internals.get(com, 0) + inc
-
-
-
-def __neighcom(node, graph, status) :
-    """
-    Compute the communities in the neighborood of node in the graph given
-    with the decomposition node2com
-    """
-    weights = {}
-    for neighbor, datas in graph[node].iteritems() :
-        if neighbor != node :
-            weight = datas.get("weight", 1)
-            neighborcom = status.node2com[neighbor]
-            weights[neighborcom] = weights.get(neighborcom, 0) + weight
-            
-    return weights
-
-
-def __remove(node, com, weight, status) :
-    """ Remove node from community com and modify status"""
-    status.degrees[com] = ( status.degrees.get(com, 0.)
-                                    - status.gdegrees.get(node, 0.) )
-    status.internals[com] = float( status.internals.get(com, 0.) -
-                weight - status.loops.get(node, 0.) )
-    status.node2com[node] = -1
-    
-
-def __insert(node, com, weight, status) :
-    """ Insert node into community and modify status"""
-    status.node2com[node] = com
-    status.degrees[com] = ( status.degrees.get(com, 0.) +
-                                status.gdegrees.get(node, 0.) )
-    status.internals[com] = float( status.internals.get(com, 0.) +
-                        weight + status.loops.get(node, 0.) )
-
-
-def __modularity(status) :
-    """
-    Compute the modularity of the partition of the graph faslty using status precomputed
-    """
-    links = float(status.total_weight)
-    result = 0.
-    for community in set(status.node2com.values()) :
-        in_degree = status.internals.get(community, 0.)
-        degree = status.degrees.get(community, 0.)
-        if links > 0 :
-            result = result + in_degree / links - ((degree / (2.*links))**2)
-    return result
-
-
-def __main() :
-    """Main function to mimic C++ version behavior"""
-    try :
-        filename = sys.argv[1]
-        graphfile = __load_binary(filename)
-        partition = best_partition(graphfile)
-        print >> sys.stderr, str(modularity(partition, graphfile))
-        for elem, part in partition.iteritems() :
-            print str(elem) + " " + str(part)
-    except (IndexError, IOError):
-        print "Usage : ./community filename"
-        print "find the communities in graph filename and display the dendogram"
-        print "Parameters:"
-        print "filename is a binary file as generated by the "
-        print "convert utility distributed with the C implementation"
-
-    
-
-if __name__ == "__main__" :
-    __main()
-
-

File community/__init__.py

+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+"""
+This module implements community detection.
+"""
+__all__ = ["partition_at_level", "modularity", "best_partition", "generate_dendogram", "induced_graph"]
+__author__ = """Thomas Aynaud (thomas.aynaud@lip6.fr)"""
+#    Copyright (C) 2009 by
+#    Thomas Aynaud <thomas.aynaud@lip6.fr>
+#    All rights reserved.
+#    BSD license.
+
+__PASS_MAX = -1
+__MIN = 0.0000001
+
+import networkx as nx
+import sys
+import types
+import array
+
+
+def partition_at_level(dendogram, level) :
+    """Return the partition of the nodes at the given level
+
+    A dendogram is a tree and each level is a partition of the graph nodes.
+    Level 0 is the first partition, which contains the smallest communities, and the best is len(dendogram) - 1.
+    The higher the level is, the bigger are the communities
+
+    Parameters
+    ----------
+    dendogram : list of dict
+       a list of partitions, ie dictionnaries where keys of the i+1 are the values of the i.
+    level : int
+       the level which belongs to [0..len(dendogram)-1]
+
+    Returns
+    -------
+    partition : dictionnary
+       A dictionary where keys are the nodes and the values are the set it belongs to
+
+    Raises
+    ------
+    KeyError
+       If the dendogram is not well formed or the level is too high
+
+    See Also
+    --------
+    best_partition which directly combines partition_at_level and generate_dendogram to obtain the partition of highest modularity
+
+    Examples
+    --------
+    >>> G=nx.erdos_renyi_graph(100, 0.01)
+    >>> dendo = generate_dendogram(G)
+    >>> for level in range(len(dendo) - 1) :
+    >>>     print "partition at level", level, "is", partition_at_level(dendo, level)
+    """
+    partition = dendogram[0].copy()
+    for index in range(1, level + 1) :
+        for node, community in partition.iteritems() :
+            partition[node] = dendogram[index][community]
+    return partition
+
+
+def modularity(partition, graph) :
+    """Compute the modularity of a partition of a graph
+
+    Parameters
+    ----------
+    partition : dict
+       the partition of the nodes, i.e a dictionary where keys are their nodes and values the communities
+    graph : networkx.Graph
+       the networkx graph which is decomposed
+
+    Returns
+    -------
+    modularity : float
+       The modularity
+
+    Raises
+    ------
+    KeyError
+       If the partition is not a partition of all graph nodes
+    ValueError
+        If the graph has no link
+    TypeError
+        If graph is not a networkx.Graph
+
+    References
+    ----------
+    .. 1. Newman, M.E.J. & Girvan, M. Finding and evaluating community structure in networks. Physical Review E 69, 26113(2004).
+
+    Examples
+    --------
+    >>> G=nx.erdos_renyi_graph(100, 0.01)
+    >>> part = best_partition(G)
+    >>> modularity(part, G)
+    """
+    if type(graph) != nx.Graph :
+        raise TypeError("Bad graph type, use only non directed graph")
+
+    inc = dict([])
+    deg = dict([])
+    links = graph.size(weight='weight')
+    if links == 0 :
+        raise ValueError("A graph without link has an undefined modularity")
+
+    for node in graph :
+        com = partition[node]
+        deg[com] = deg.get(com, 0.) + graph.degree(node, weight = 'weight')
+        for neighbor, datas in graph[node].iteritems() :
+            weight = datas.get("weight", 1)
+            if partition[neighbor] == com :
+                if neighbor == node :
+                    inc[com] = inc.get(com, 0.) + float(weight)
+                else :
+                    inc[com] = inc.get(com, 0.) + float(weight) / 2.
+
+    res = 0.
+    for com in set(partition.values()) :
+        res += (inc.get(com, 0.) / links) - (deg.get(com, 0.) / (2.*links))**2
+    return res
+
+
+def best_partition(graph, partition = None) :
+    """Compute the partition of the graph nodes which maximises the modularity
+    (or try..) using the Louvain heuristices
+
+    This is the partition of highest modularity, i.e. the highest partition of the dendogram
+    generated by the Louvain algorithm.
+
+    Parameters
+    ----------
+    graph : networkx.Graph
+       the networkx graph which is decomposed
+    partition : dict, optionnal
+       the algorithm will start using this partition of the nodes. It's a dictionary where keys are their nodes and values the communities
+
+    Returns
+    -------
+    partition : dictionnary
+       The partition, with communities numbered from 0 to number of communities
+
+    Raises
+    ------
+    NetworkXError
+       If the graph is not Eulerian.
+
+    See Also
+    --------
+    generate_dendogram to obtain all the decompositions levels
+
+    Notes
+    -----
+    Uses Louvain algorithm
+
+    References
+    ----------
+    .. 1. Blondel, V.D. et al. Fast unfolding of communities in large networks. J. Stat. Mech 10008, 1-12(2008).
+
+    Examples
+    --------
+    >>>  #Basic usage
+    >>> G=nx.erdos_renyi_graph(100, 0.01)
+    >>> part = best_partition(G)
+
+    >>> #other example to display a graph with its community :
+    >>> #better with karate_graph() as defined in networkx examples
+    >>> #erdos renyi don't have true community structure
+    >>> G = nx.erdos_renyi_graph(30, 0.05)
+    >>> #first compute the best partition
+    >>> partition = community.best_partition(G)
+    >>>  #drawing
+    >>> size = float(len(set(partition.values())))
+    >>> pos = nx.spring_layout(G)
+    >>> count = 0.
+    >>> for com in set(partition.values()) :
+    >>>     count = count + 1.
+    >>>     list_nodes = [nodes for nodes in partition.keys()
+    >>>                                 if partition[nodes] == com]
+    >>>     nx.draw_networkx_nodes(G, pos, list_nodes, node_size = 20,
+                                    node_color = str(count / size))
+    >>> nx.draw_networkx_edges(G,pos, alpha=0.5)
+    >>> plt.show()
+    """
+    dendo = generate_dendogram(graph, partition)
+    return partition_at_level(dendo, len(dendo) - 1 )
+
+
+def generate_dendogram(graph, part_init = None) :
+    """Find communities in the graph and return the associated dendogram
+
+    A dendogram is a tree and each level is a partition of the graph nodes.  Level 0 is the first partition, which contains the smallest communities, and the best is len(dendogram) - 1. The higher the level is, the bigger are the communities
+
+
+    Parameters
+    ----------
+    graph : networkx.Graph
+        the networkx graph which will be decomposed
+    part_init : dict, optionnal
+        the algorithm will start using this partition of the nodes. It's a dictionary where keys are their nodes and values the communities
+
+    Returns
+    -------
+    dendogram : list of dictionaries
+        a list of partitions, ie dictionnaries where keys of the i+1 are the values of the i. and where keys of the first are the nodes of graph
+
+    Raises
+    ------
+    TypeError
+        If the graph is not a networkx.Graph
+
+    See Also
+    --------
+    best_partition
+
+    Notes
+    -----
+    Uses Louvain algorithm
+
+    References
+    ----------
+    .. 1. Blondel, V.D. et al. Fast unfolding of communities in large networks. J. Stat. Mech 10008, 1-12(2008).
+
+    Examples
+    --------
+    >>> G=nx.erdos_renyi_graph(100, 0.01)
+    >>> dendo = generate_dendogram(G)
+    >>> for level in range(len(dendo) - 1) :
+    >>>     print "partition at level", level, "is", partition_at_level(dendo, level)
+    """
+    if type(graph) != nx.Graph :
+        raise TypeError("Bad graph type, use only non directed graph")
+
+    #special case, when there is no link
+    #the best partition is everyone in its community
+    if graph.number_of_edges() == 0 :
+        part = dict([])
+        for node in graph.nodes() :
+            part[node] = node
+        return part
+
+    current_graph = graph.copy()
+    status = Status()
+    status.init(current_graph, part_init)
+    mod = __modularity(status)
+    status_list = list()
+    __one_level(current_graph, status)
+    new_mod = __modularity(status)
+    partition = __renumber(status.node2com)
+    status_list.append(partition)
+    mod = new_mod
+    current_graph = induced_graph(partition, current_graph)
+    status.init(current_graph)
+
+    while True :
+        __one_level(current_graph, status)
+        new_mod = __modularity(status)
+        if new_mod - mod < __MIN :
+            break
+        partition = __renumber(status.node2com)
+        status_list.append(partition)
+        mod = new_mod
+        current_graph = induced_graph(partition, current_graph)
+        status.init(current_graph)
+    return status_list[:]
+
+
+def induced_graph(partition, graph) :
+    """Produce the graph where nodes are the communities
+
+    there is a link of weight w between communities if the sum of the weights of the links between their elements is w
+
+    Parameters
+    ----------
+    partition : dict
+       a dictionary where keys are graph nodes and  values the part the node belongs to
+    graph : networkx.Graph
+        the initial graph
+
+    Returns
+    -------
+    g : networkx.Graph
+       a networkx graph where nodes are the parts
+
+    Examples
+    --------
+    >>> n = 5
+    >>> g = nx.complete_graph(2*n)
+    >>> part = dict([])
+    >>> for node in g.nodes() :
+    >>>     part[node] = node % 2
+    >>> ind = induced_graph(part, g)
+    >>> goal = nx.Graph()
+    >>> goal.add_weighted_edges_from([(0,1,n*n),(0,0,n*(n-1)/2), (1, 1, n*(n-1)/2)])
+    >>> nx.is_isomorphic(int, goal)
+    True
+    """
+    ret = nx.Graph()
+    ret.add_nodes_from(partition.values())
+
+    for node1, node2, datas in graph.edges_iter(data = True) :
+        weight = datas.get("weight", 1)
+        com1 = partition[node1]
+        com2 = partition[node2]
+        w_prec = ret.get_edge_data(com1, com2, {"weight":0}).get("weight", 1)
+        ret.add_edge(com1, com2, weight = w_prec + weight)
+
+    return ret
+
+
+def __renumber(dictionary) :
+    """Renumber the values of the dictionary from 0 to n
+    """
+    count = 0
+    ret = dictionary.copy()
+    new_values = dict([])
+
+    for key in dictionary.keys() :
+        value = dictionary[key]
+        new_value = new_values.get(value, -1)
+        if new_value == -1 :
+            new_values[value] = count
+            new_value = count
+            count = count + 1
+        ret[key] = new_value
+
+    return ret
+
+
+def __load_binary(data) :
+    """Load binary graph as used by the cpp implementation of this algorithm
+    """
+    if type(data) == types.StringType :
+        data = open(data, "rb")
+
+    reader = array.array("I")
+    reader.fromfile(data, 1)
+    num_nodes = reader.pop()
+    reader = array.array("I")
+    reader.fromfile(data, num_nodes)
+    cum_deg = reader.tolist()
+    num_links = reader.pop()
+    reader = array.array("I")
+    reader.fromfile(data, num_links)
+    links = reader.tolist()
+    graph = nx.Graph()
+    graph.add_nodes_from(range(num_nodes))
+    prec_deg = 0
+
+    for index in range(num_nodes) :
+        last_deg = cum_deg[index]
+        neighbors = links[prec_deg:last_deg]
+        graph.add_edges_from([(index, int(neigh)) for neigh in neighbors])
+        prec_deg = last_deg
+
+    return graph
+
+
+def __one_level(graph, status) :
+    """Compute one level of communities
+    """
+    modif = True
+    nb_pass_done = 0
+    cur_mod = __modularity(status)
+    new_mod = cur_mod
+
+    while modif  and nb_pass_done != __PASS_MAX :
+        cur_mod = new_mod
+        modif = False
+        nb_pass_done += 1
+
+        for node in graph.nodes() :
+            com_node = status.node2com[node]
+            degc_totw = status.gdegrees.get(node, 0.) / (status.total_weight*2.)
+            neigh_communities = __neighcom(node, graph, status)
+            __remove(node, com_node,
+                    neigh_communities.get(com_node, 0.), status)
+            best_com = com_node
+            best_increase = 0
+            for com, dnc in neigh_communities.iteritems() :
+                incr =  dnc  - status.degrees.get(com, 0.) * degc_totw
+                if incr > best_increase :
+                    best_increase = incr
+                    best_com = com
+            __insert(node, best_com,
+                    neigh_communities.get(best_com, 0.), status)
+            if best_com != com_node :
+                modif = True
+        new_mod = __modularity(status)
+        if new_mod - cur_mod < __MIN :
+            break
+
+
+class Status :
+    """
+    To handle several data in one struct.
+
+    Could be replaced by named tuple, but don't want to depend on python 2.6
+    """
+    node2com = {}
+    total_weight = 0
+    internals = {}
+    degrees = {}
+    gdegrees = {}
+
+    def __init__(self) :
+        self.node2com = dict([])
+        self.total_weight = 0
+        self.degrees = dict([])
+        self.gdegrees = dict([])
+        self.internals = dict([])
+        self.loops = dict([])
+
+    def __str__(self) :
+        return ("node2com : " + str(self.node2com) + " degrees : "
+            + str(self.degrees) + " internals : " + str(self.internals)
+            + " total_weight : " + str(self.total_weight))
+
+    def copy(self) :
+        """Perform a deep copy of status"""
+        new_status = Status()
+        new_status.node2com = self.node2com.copy()
+        new_status.internals = self.internals.copy()
+        new_status.degrees = self.degrees.copy()
+        new_status.gdegrees = self.gdegrees.copy()
+        new_status.total_weight = self.total_weight
+
+    def init(self, graph, part = None) :
+        """Initialize the status of a graph with every node in one community"""
+        count = 0
+        self.node2com = dict([])
+        self.total_weight = 0
+        self.degrees = dict([])
+        self.gdegrees = dict([])
+        self.internals = dict([])
+        self.total_weight = graph.size(weight = 'weight')
+        if part == None :
+            for node in graph.nodes() :
+                self.node2com[node] = count
+                deg = float(graph.degree(node, weight = 'weight'))
+                if deg < 0 :
+                    raise ValueError("Bad graph type, use positive weights")
+                self.degrees[count] = deg
+                self.gdegrees[node] = deg
+                self.loops[node] = float(graph.get_edge_data(node, node,
+                                                 {"weight":0}).get("weight", 1))
+                self.internals[count] = self.loops[node]
+                count = count + 1
+        else :
+            for node in graph.nodes() :
+                com = part[node]
+                self.node2com[node] = com
+                deg = float(graph.degree(node, weigh = 'weight'))
+                self.degrees[com] = self.degrees.get(com, 0) + deg
+                self.gdegrees[node] = deg
+                inc = 0.
+                for neighbor, datas in graph[node].iteritems() :
+                    weight = datas.get("weight", 1)
+                    if weight <= 0 :
+                        raise ValueError("Bad graph type, use positive weights")
+                    if part[neighbor] == com :
+                        if neighbor == node :
+                            inc += float(weight)
+                        else :
+                            inc += float(weight) / 2.
+                self.internals[com] = self.internals.get(com, 0) + inc
+
+
+
+def __neighcom(node, graph, status) :
+    """
+    Compute the communities in the neighborood of node in the graph given
+    with the decomposition node2com
+    """
+    weights = {}
+    for neighbor, datas in graph[node].iteritems() :
+        if neighbor != node :
+            weight = datas.get("weight", 1)
+            neighborcom = status.node2com[neighbor]
+            weights[neighborcom] = weights.get(neighborcom, 0) + weight
+
+    return weights
+
+
+def __remove(node, com, weight, status) :
+    """ Remove node from community com and modify status"""
+    status.degrees[com] = ( status.degrees.get(com, 0.)
+                                    - status.gdegrees.get(node, 0.) )
+    status.internals[com] = float( status.internals.get(com, 0.) -
+                weight - status.loops.get(node, 0.) )
+    status.node2com[node] = -1
+
+
+def __insert(node, com, weight, status) :
+    """ Insert node into community and modify status"""
+    status.node2com[node] = com
+    status.degrees[com] = ( status.degrees.get(com, 0.) +
+                                status.gdegrees.get(node, 0.) )
+    status.internals[com] = float( status.internals.get(com, 0.) +
+                        weight + status.loops.get(node, 0.) )
+
+
+def __modularity(status) :
+    """
+    Compute the modularity of the partition of the graph faslty using status precomputed
+    """
+    links = float(status.total_weight)
+    result = 0.
+    for community in set(status.node2com.values()) :
+        in_degree = status.internals.get(community, 0.)
+        degree = status.degrees.get(community, 0.)
+        if links > 0 :
+            result = result + in_degree / links - ((degree / (2.*links))**2)
+    return result
+
+
+def main() :
+    """Main function to mimic C++ version behavior"""
+    try :
+        filename = sys.argv[1]
+        graphfile = __load_binary(filename)
+        partition = best_partition(graphfile)
+        print >> sys.stderr, str(modularity(partition, graphfile))
+        for elem, part in partition.iteritems() :
+            print str(elem) + " " + str(part)
+    except (IndexError, IOError):
+        print "Usage : ./community filename"
+        print "find the communities in graph filename and display the dendogram"
+        print "Parameters:"
+        print "filename is a binary file as generated by the "
+        print "convert utility distributed with the C implementation"

File conf.py

-# -*- coding: utf-8 -*-
-#
-# Community detection for NetworkX documentation build configuration file, created by
-# sphinx-quickstart on Fri Jan 15 11:13:59 2010.
-#
-# This file is execfile()d with the current directory set to its containing dir.
-#
-# Note that not all possible configuration values are present in this
-# autogenerated file.
-#
-# All configuration values have a default; values that are commented out
-# serve to show the default.
-
-import sys, os
-
-import community
-# If extensions (or modules to document with autodoc) are in another directory,
-# add these directories to sys.path here. If the directory is relative to the
-# documentation root, use os.path.abspath to make it absolute, like shown here.
-#sys.path.append(os.path.abspath('.'))
-
-# -- General configuration -----------------------------------------------------
-
-# Add any Sphinx extension module names here, as strings. They can be extensions
-# coming with Sphinx (named 'sphinx.ext.*') or your custom ones.
-extensions = ['sphinx.ext.autodoc', 'sphinx.ext.doctest', 'sphinx.ext.coverage', 'sphinx.ext.autosummary', 'numpydoc']
-
-# Add any paths that contain templates here, relative to this directory.
-templates_path = ['_templates']
-
-
-autodoc_member_order = "groupwise"
-autosummary_generate = ["api"]
-
-
-# The suffix of source filenames.
-source_suffix = '.rst'
-
-# The encoding of source files.
-#source_encoding = 'utf-8'
-
-# The master toctree document.
-master_doc = 'index'
-
-# General information about the project.
-project = u'Community detection for NetworkX'
-copyright = u'2010, Thomas Aynaud'
-
-# The version info for the project you're documenting, acts as replacement for
-# |version| and |release|, also used in various other places throughout the
-# built documents.
-#
-# The short X.Y version.
-version = '1'
-# The full version, including alpha/beta/rc tags.
-release = '2'
-
-# The language for content autogenerated by Sphinx. Refer to documentation
-# for a list of supported languages.
-#language = None
-
-# There are two options for replacing |today|: either, you set today to some
-# non-false value, then it is used:
-#today = ''
-# Else, today_fmt is used as the format for a strftime call.
-#today_fmt = '%B %d, %Y'
-
-# List of documents that shouldn't be included in the build.
-#unused_docs = []
-
-# List of directories, relative to source directory, that shouldn't be searched
-# for source files.
-exclude_trees = ['_build']
-
-# The reST default role (used for this markup: `text`) to use for all documents.
-#default_role = None
-
-# If true, '()' will be appended to :func: etc. cross-reference text.
-#add_function_parentheses = True
-
-# If true, the current module name will be prepended to all description
-# unit titles (such as .. function::).
-#add_module_names = True
-
-# If true, sectionauthor and moduleauthor directives will be shown in the
-# output. They are ignored by default.
-#show_authors = False
-
-# The name of the Pygments (syntax highlighting) style to use.
-pygments_style = 'sphinx'
-
-# A list of ignored prefixes for module index sorting.
-#modindex_common_prefix = []
-
-
-# -- Options for HTML output ---------------------------------------------------
-
-# The theme to use for HTML and HTML Help pages.  Major themes that come with
-# Sphinx are currently 'default' and 'sphinxdoc'.
-html_theme = 'default'
-
-# Theme options are theme-specific and customize the look and feel of a theme
-# further.  For a list of options available for each theme, see the
-# documentation.
-#html_theme_options = {}
-
-# Add any paths that contain custom themes here, relative to this directory.
-#html_theme_path = []
-
-# The name for this set of Sphinx documents.  If None, it defaults to
-# "<project> v<release> documentation".
-#html_title = None
-
-# A shorter title for the navigation bar.  Default is the same as html_title.
-#html_short_title = None
-
-# The name of an image file (relative to this directory) to place at the top
-# of the sidebar.
-#html_logo = None
-
-# The name of an image file (within the static path) to use as favicon of the
-# docs.  This file should be a Windows icon file (.ico) being 16x16 or 32x32
-# pixels large.
-#html_favicon = None
-
-# Add any paths that contain custom static files (such as style sheets) here,
-# relative to this directory. They are copied after the builtin static files,
-# so a file named "default.css" will overwrite the builtin "default.css".
-html_static_path = ['_static']
-
-# If not '', a 'Last updated on:' timestamp is inserted at every page bottom,
-# using the given strftime format.
-#html_last_updated_fmt = '%b %d, %Y'
-
-# If true, SmartyPants will be used to convert quotes and dashes to
-# typographically correct entities.
-#html_use_smartypants = True
-
-# Custom sidebar templates, maps document names to template names.
-#html_sidebars = {}
-
-# Additional templates that should be rendered to pages, maps page names to
-# template names.
-#html_additional_pages = {}
-
-# If false, no module index is generated.
-#html_use_modindex = True
-
-# If false, no index is generated.
-#html_use_index = True
-
-# If true, the index is split into individual pages for each letter.
-#html_split_index = False
-
-# If true, links to the reST sources are added to the pages.
-#html_show_sourcelink = True
-
-# If true, an OpenSearch description file will be output, and all pages will
-# contain a <link> tag referring to it.  The value of this option must be the
-# base URL from which the finished HTML is served.
-#html_use_opensearch = ''
-
-# If nonempty, this is the file name suffix for HTML files (e.g. ".xhtml").
-#html_file_suffix = ''
-
-# Output file base name for HTML help builder.
-htmlhelp_basename = 'CommunitydetectionforNetworkXdoc'
-
-
-# -- Options for LaTeX output --------------------------------------------------
-
-# The paper size ('letter' or 'a4').
-#latex_paper_size = 'letter'
-
-# The font size ('10pt', '11pt' or '12pt').
-#latex_font_size = '10pt'
-
-# Grouping the document tree into LaTeX files. List of tuples
-# (source start file, target name, title, author, documentclass [howto/manual]).
-latex_documents = [
-  ('index', 'CommunitydetectionforNetworkX.tex', u'Community detection for NetworkX Documentation',
-   u'Thomas Aynaud', 'manual'),
-]
-
-# The name of an image file (relative to this directory) to place at the top of
-# the title page.
-#latex_logo = None
-
-# For "manual" documents, if this is true, then toplevel headings are parts,
-# not chapters.
-#latex_use_parts = False
-
-# Additional stuff for the LaTeX preamble.
-#latex_preamble = ''
-
-# Documents to append as an appendix to all manuals.
-#latex_appendices = []
-
-# If false, no module index is generated.
-#latex_use_modindex = True

File docs/Makefile

+# Makefile for Sphinx documentation
+#
+
+EXEC= html
+
+
+# You can set these variables from the command line.
+SPHINXOPTS    =
+SPHINXBUILD   = sphinx-build
+PAPER         =
+BUILDDIR      = _build
+
+# Internal variables.
+PAPEROPT_a4     = -D latex_paper_size=a4
+PAPEROPT_letter = -D latex_paper_size=letter
+ALLSPHINXOPTS   = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) .
+
+.PHONY: help clean html dirhtml pickle json htmlhelp qthelp latex changes linkcheck doctest
+
+all: $(EXEC)
+	
+#########################################
+# Generic rules
+##########################################
+
+
+clean:
+	-rm -rf $(BUILDDIR)/*
+
+help:
+	@echo "Please use \`make <target>' where <target> is one of"
+	@echo "  html      to make standalone HTML files"
+	@echo "  dirhtml   to make HTML files named index.html in directories"
+	@echo "  pickle    to make pickle files"
+	@echo "  json      to make JSON files"
+	@echo "  htmlhelp  to make HTML files and a HTML help project"
+	@echo "  qthelp    to make HTML files and a qthelp project"
+	@echo "  latex     to make LaTeX files, you can set PAPER=a4 or PAPER=letter"
+	@echo "  changes   to make an overview of all changed/added/deprecated items"
+	@echo "  linkcheck to check all external links for integrity"
+	@echo "  doctest   to run all doctests embedded in the documentation (if enabled)"
+
+
+html:
+	$(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html
+	@echo
+	@echo "Build finished. The HTML pages are in $(BUILDDIR)/html."
+
+dirhtml:
+	$(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml
+	@echo
+	@echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml."
+
+pickle:
+	$(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle
+	@echo
+	@echo "Build finished; now you can process the pickle files."
+
+json:
+	$(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json
+	@echo
+	@echo "Build finished; now you can process the JSON files."
+
+htmlhelp:
+	$(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp
+	@echo
+	@echo "Build finished; now you can run HTML Help Workshop with the" \
+	      ".hhp project file in $(BUILDDIR)/htmlhelp."
+
+qthelp:
+	$(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp
+	@echo
+	@echo "Build finished; now you can run "qcollectiongenerator" with the" \
+	      ".qhcp project file in $(BUILDDIR)/qthelp, like this:"
+	@echo "# qcollectiongenerator $(BUILDDIR)/qthelp/CommunitydetectionforNetworkX.qhcp"
+	@echo "To view the help file:"
+	@echo "# assistant -collectionFile $(BUILDDIR)/qthelp/CommunitydetectionforNetworkX.qhc"
+
+latex:
+	$(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
+	@echo
+	@echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex."
+	@echo "Run \`make all-pdf' or \`make all-ps' in that directory to" \
+	      "run these through (pdf)latex."
+
+changes:
+	$(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes
+	@echo
+	@echo "The overview file is in $(BUILDDIR)/changes."
+
+linkcheck:
+	$(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck
+	@echo
+	@echo "Link check complete; look for any errors in the above output " \
+	      "or in $(BUILDDIR)/linkcheck/output.txt."
+
+doctest:
+	$(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest
+	@echo "Testing of doctests in the sources finished, look at the " \
+	      "results in $(BUILDDIR)/doctest/output.txt."

File docs/_static/default.css

+/**
+ * Alternate Sphinx design
+ * Originally created by Armin Ronacher for Werkzeug, adapted by Georg Brandl.
+ */
+
+body {
+    font-family: 'Lucida Grande', 'Lucida Sans Unicode', 'Geneva', 'Verdana', sans-serif;
+    font-size: 14px;
+    letter-spacing: -0.01em;
+    line-height: 150%;
+    text-align: center;
+    /*background-color: #AFC1C4; */
+    background-color: #BFD1D4;
+    color: black;
+    padding: 0;
+    border: 1px solid #aaa;
+
+    margin: 0px 80px 0px 80px;
+    min-width: 740px;
+}
+
+a {
+    color: #CA7900;
+    text-decoration: none;
+}
+
+a:hover {
+    color: #2491CF;
+}
+
+pre {
+    font-family: 'Consolas', 'Deja Vu Sans Mono', 'Bitstream Vera Sans Mono', monospace;
+    font-size: 0.95em;
+    letter-spacing: 0.015em;
+    padding: 0.5em;
+    border: 1px solid #ccc;
+    background-color: #f8f8f8;
+}
+
+td.linenos pre {
+    padding: 0.5em 0;
+    border: 0;
+    background-color: transparent;
+    color: #aaa;
+}
+
+table.highlighttable {
+    margin-left: 0.5em;
+}
+
+table.highlighttable td {
+    padding: 0 0.5em 0 0.5em;
+}
+
+cite, code, tt {
+    font-family: 'Consolas', 'Deja Vu Sans Mono', 'Bitstream Vera Sans Mono', monospace;
+    font-size: 0.95em;
+    letter-spacing: 0.01em;
+}
+
+hr {
+    border: 1px solid #abc;
+    margin: 2em;
+}
+
+tt {
+    background-color: #f2f2f2;
+    border-bottom: 1px solid #ddd;
+    color: #333;
+}
+
+tt.descname {
+    background-color: transparent;
+    font-weight: bold;
+    font-size: 1.2em;
+    border: 0;
+}
+
+tt.descclassname {
+    background-color: transparent;
+    border: 0;
+}
+
+tt.xref {
+    background-color: transparent;
+    font-weight: bold;
+    border: 0;
+}
+
+a tt {
+    background-color: transparent;
+    font-weight: bold;
+    border: 0;
+    color: #CA7900;
+}
+
+a tt:hover {
+    color: #2491CF;
+}