infomod Files

---INFOMOD---

anil raj ( ar2384@columbia.edu )
chris wiggins ( chris.wiggins@columbia.edu )

release version {FIXME}

introduction
---------
code in MATLAB to quantify the modularity of a graph,
defined via a multi-scale, information-theoretic measure of
the summarizability of the graph in terms of modules,
while also producing a list of modules at all scales
(a.k.a "community detection").

this software is free for scientific use. please contact us if you
plan to use this software for commercial purposes. do not further
distribute without prior permission of the authors. if used in your
scientific work, please cite as:

@article{ 2005:Ziv05:infomod,
 eprint       = {q-bio/0411033},
 author       = {E. Ziv and M. Middendorf and C. H. Wiggins},
 editor       = {2005/05/21 09:00},
 title        = {Information-theoretic approach to network modularity.},
 journal      = {Physical Review E},
 volume       = {71(4 Pt 2)},
 pages        = {046117. Epub 2005 Apr 14.},
 month        = {Apr},
 year         = {2005},
 abstract     = {Exploiting recent developments in information theory, we propose, illustrate, and validate a principled information-theoretic algorithm for
 module discovery and the resulting measure of network modularity. This
 measure is an order parameter (a dimensionless number between 0 and 1).
 Comparison is made with other approaches to module discovery and to
 quantifying network modularity (using Monte Carlo generated Erdo s-like
 modular networks). Finally, the network information bottleneck (NIB)
 algorithm is applied to a number of real world networks, including the
 "social" network of coauthors at the 2004 APS March Meeting.},
 keywords = {2005/05/21 09:00}
 },

please cite this work if you use this code in publications.

the code implements the simplest approximation to the optimization
described in the manuscript, i.e., 
hierarchical agglomerative pairwise clustering.

an additional technical necessity was a novel numerical implementation
of the JS entropy calculation (a similarity measure) for small JS-divergences.

the JS calculation is described in the report

@article{ 2008:Raj08:jsdiv,
 archivePrefix= {arXiv},
 primaryClass = {stat.ML},
 eprint       = {0810.5117},
 author       = {A. Raj and C. H. Wiggins},
 title        = {A non-negative expansion for small Jensen-Shannon
Divergences},
 month        = {Oct},
 year         = {2008},
 abstract     = {In this report, we derive a non-negative series expansion for
the Jensen-Shannon divergence (JSD) between two probability distributions.
This series expansion is shown to be useful for numerical calculations of the
JSD, when the probability distributions are nearly equal, and for which,
consequently, small numerical errors dominate evaluation.},
 url          = {http://arxiv.org/abs/0810.5117}
}

please cite this work if you use this code in publications.

installation
----------
infomod doesn't require any installation, it just requires all
m-files be in matlab's path. this is possible by making this directory your
current directory when running the code or by adding it to your path.

---USAGE:---

the 'main' routine is infomod.m. please read the comments 
(the lines that start with '%' for usage)

example call: run infomod on an erdos renyi graph of density .2, 
assuming uniform prior over nodes and evaluating JS to order 4.

infomod(rand(10)<.4,1,4)

license 
----------
copyright (c) 2004, 2008 chris wiggins <chris.wiggins@columbia.edu>

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.