DEMON

Democratic Estimate of the Modular Organization of a Network

Implemented by Giulio Rossetti

DEMON is an algorithm for detecting overlapping communities in complex networks. Intuitively, communities are set of nodes densely connected to each other (although there are other definitions of a community in a network). Overlapping communities allow nodes to be in different communities at the same time. The paper describing DEMON’s implementation can be downloaded here.

The code is available for download in a Python format. You can download the archive. The ZIP file contains two files: Demon.py that is the proper implementation of Demon, and launch.py that provides an example of how to use Demon.py. Just put Demon.py in the folder where you’ll run your script and use a launch.py file to execute Demon on your network. You’ll need to build the network as a Networkx object and then to pass it to the execute method of Demon with optional parameters (epsilon, whether the network is weighted or not and the minimum size of the communities).

The output will be a list of communities. One community per line. The id of the community will be the first thing on the line followed by a tab and then the list of nodes belonging to the community, separated by commas.

DEMON requires a particular input format to work. For this reason, in this page you can find three examples of networks available for the download in DEMON’s format [UPDATE: the new Python implementation of DEMON fixes some bugs and actually requires only the edge list file, the node list file is NOT required anymore]:

  • Congress: The network of legislative collaborations between US representatives of the House and the Senate during the 111st US congress (2009-2011). We downloaded the data about all the bills discussed during the last Congress from GovTrack, a web-based service recording the activities of each member of the US Congress. The bills are usually cosponsored by many politicians. We connected politicians if they have at least 75 co-sponsorships and deleted all the connections that were created only by bills with more than 10 co-sponsors. Attached to each bill in the Govtrack data we have also a collection of subjects related to the bill. The set of subjects a politicians frequently worked on is the qualitative attribute of this network (download the attributes).
  • IMDb: We downloaded the entire database of IMDb from their official APIs on August 25th 2011. We focused on actors who starred in at least two movies during the years from 2001 to 2010, filtering out television shows, video games, and other performances. We connected actors with at least two movies in which they both appeared. This network is weighted according to the number of co-appearances. Our qualitative attributes are the user assigned keywords summarizing the movies each actor has been part of. Network attributes for the nodes downloadable at IMDb; but you’ll need the map actor -> network ID.
  • Amazon: The Amazon network and attributes are available for download at the SNAP Network Collection.

Happy community finding!