{"action":"created","comment":{"url":"https://api.github.com/repos/networkx/networkx/pulls/comments/35889828","id":35889828,"diff_hunk":"@@ -0,0 +1,236 @@\n+# -*- coding: utf-8 -*-\n+#    Copyright Giulio Rossetti, Michele Coscia (C) 2015\n+#    All rights reserved.\n+#    BSD license.\n+\n+\"\"\"\n+Flat Merge version of DEMON (Democratic Estimate of the Modular Organization of\n+a Network) algorithm. DEMON uses a local-first approach to community discovery \n+were each node democratically votes for the communities that it sees in its\n+surroundings. It provides a deterministic, fully incremental method for \n+community discovery that has a limited time complexity.\n+\"\"\"\n+\n+from __future__ import division\n+import networkx as nx\n+import random\n+from collections import defaultdict\n+\n+\n+__all__ = [\"demon_communities\"]\n+\n+\n+def demon_communities(G, epsilon=0.25, min_community_size=3, weight=None):\n+    \"\"\"Finds the communities in a graph using the label Democratic Estimate of\n+    the Modular Organization of a Network (DEMON) algorithm[1]_. This method\n+    uses a local-first approach to community discovery were each node\n+    democratically votes for the communities that it sees in its surroundings.\n+    Communities in this algorithm can be overlapping.\n+\n+    Parameters\n+    ----------\n+    G : graph\n+        A NetworkX graph.\n+\n+    epsilon: real\n+        The tolerance required in order to merge communities. The epsilon\n+        factor is introduced to vary the percentage of common elements provided\n+        from each couple of communities: epsilon = 0 ensure that two\n+        communities are merged only if one of them is a proper subset of the\n+        other, on the other hand with a value of epsilon = 1 even communities\n+        that do not share a single node are merged together\n+\n+    min_community_size: integer\n+        Min nodes needed to form a community\n+\n+    weight: String\n+        If the graph is weighted, the edge parameter representing the weight\n+\n+    Returns\n+    -------\n+    communities : list\n+        List of overlapping communities (sets)\n+\n+    References\n+    ----------\n+    .. [1] Michele Coscia, Giulio Rossetti, Fosca Giannotti, Dino Pedreschi:\n+           DEMON: a local-first discovery method for overlapping communities.\n+           KDD 2012:615-623.\n+    \"\"\"\n+\n+    all_communities = []\n+\n+    for ego in G:\n+        # EgoMinusEgo and LabelPropagation phase\n+        ego_minus_ego = nx.ego_graph(G, ego, 1, False)","path":"networkx/algorithms/community/demon.py","position":65,"original_position":65,"commit_id":"29d330533e2987b57264fe61341a12ce7b12f388","original_commit_id":"29d330533e2987b57264fe61341a12ce7b12f388","user":{"login":"jfinkels","id":121755,"avatar_url":"https://avatars.githubusercontent.com/u/121755?v=3","gravatar_id":"","url":"https://api.github.com/users/jfinkels","html_url":"https://github.com/jfinkels","followers_url":"https://api.github.com/users/jfinkels/followers","following_url":"https://api.github.com/users/jfinkels/following{/other_user}","gists_url":"https://api.github.com/users/jfinkels/gists{/gist_id}","starred_url":"https://api.github.com/users/jfinkels/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jfinkels/subscriptions","organizations_url":"https://api.github.com/users/jfinkels/orgs","repos_url":"https://api.github.com/users/jfinkels/repos","events_url":"https://api.github.com/users/jfinkels/events{/privacy}","received_events_url":"https://api.github.com/users/jfinkels/received_events","type":"User","site_admin":false},"body":"Better to just do `G.subgraph(G[ego])`.","created_at":"2015-07-30T16:26:21Z","updated_at":"2015-07-30T16:26:21Z","html_url":"https://github.com/networkx/networkx/pull/1560#discussion_r35889828","pull_request_url":"https://api.github.com/repos/networkx/networkx/pulls/1560","_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments/35889828"},"html":{"href":"https://github.com/networkx/networkx/pull/1560#discussion_r35889828"},"pull_request":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1560"}}},"pull_request":{"url":"https://api.github.com/repos/networkx/networkx/pulls/1560","id":36808055,"html_url":"https://github.com/networkx/networkx/pull/1560","diff_url":"https://github.com/networkx/networkx/pull/1560.diff","patch_url":"https://github.com/networkx/networkx/pull/1560.patch","issue_url":"https://api.github.com/repos/networkx/networkx/issues/1560","number":1560,"state":"open","locked":false,"title":"Democratic Estimate of the Modular Organization of a Network","user":{"login":"aitoralmeida","id":2103213,"avatar_url":"https://avatars.githubusercontent.com/u/2103213?v=3","gravatar_id":"","url":"https://api.github.com/users/aitoralmeida","html_url":"https://github.com/aitoralmeida","followers_url":"https://api.github.com/users/aitoralmeida/followers","following_url":"https://api.github.com/users/aitoralmeida/following{/other_user}","gists_url":"https://api.github.com/users/aitoralmeida/gists{/gist_id}","starred_url":"https://api.github.com/users/aitoralmeida/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aitoralmeida/subscriptions","organizations_url":"https://api.github.com/users/aitoralmeida/orgs","repos_url":"https://api.github.com/users/aitoralmeida/repos","events_url":"https://api.github.com/users/aitoralmeida/events{/privacy}","received_events_url":"https://api.github.com/users/aitoralmeida/received_events","type":"User","site_admin":false},"body":"Flat Merge version of DEMON (Democratic Estimate of the Modular Organization of a Network) algorithm as described in:\r\n\r\nMichele Coscia, Giulio Rossetti, Fosca Giannotti, Dino Pedreschi:\r\nDEMON: a local-first discovery method for overlapping communities.\r\nKDD 2012:615-623\r\n\r\nDEMON uses a local-first approach to community discovery were each node democratically votes for the communities that it sees in its surroundings. It provides a deterministic, fully incremental method for community discovery that has a limited time complexity.\r\n\r\nBased on the implementation by Giulio Rossetti <giulio.rossetti@isti.cnr.it>: http://www.michelecoscia.com/wp-content/uploads/2013/07/demon_py.zip\r\n","created_at":"2015-06-03T08:17:51Z","updated_at":"2015-07-30T16:26:21Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b030a3de1f4ecd7318c31bdd713f47674ad13c06","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/networkx/networkx/pulls/1560/commits","review_comments_url":"https://api.github.com/repos/networkx/networkx/pulls/1560/comments","review_comment_url":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/1560/comments","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/29d330533e2987b57264fe61341a12ce7b12f388","head":{"label":"aitoralmeida:demon","ref":"demon","sha":"29d330533e2987b57264fe61341a12ce7b12f388","user":{"login":"aitoralmeida","id":2103213,"avatar_url":"https://avatars.githubusercontent.com/u/2103213?v=3","gravatar_id":"","url":"https://api.github.com/users/aitoralmeida","html_url":"https://github.com/aitoralmeida","followers_url":"https://api.github.com/users/aitoralmeida/followers","following_url":"https://api.github.com/users/aitoralmeida/following{/other_user}","gists_url":"https://api.github.com/users/aitoralmeida/gists{/gist_id}","starred_url":"https://api.github.com/users/aitoralmeida/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aitoralmeida/subscriptions","organizations_url":"https://api.github.com/users/aitoralmeida/orgs","repos_url":"https://api.github.com/users/aitoralmeida/repos","events_url":"https://api.github.com/users/aitoralmeida/events{/privacy}","received_events_url":"https://api.github.com/users/aitoralmeida/received_events","type":"User","site_admin":false},"repo":{"id":24717231,"name":"networkx","full_name":"aitoralmeida/networkx","owner":{"login":"aitoralmeida","id":2103213,"avatar_url":"https://avatars.githubusercontent.com/u/2103213?v=3","gravatar_id":"","url":"https://api.github.com/users/aitoralmeida","html_url":"https://github.com/aitoralmeida","followers_url":"https://api.github.com/users/aitoralmeida/followers","following_url":"https://api.github.com/users/aitoralmeida/following{/other_user}","gists_url":"https://api.github.com/users/aitoralmeida/gists{/gist_id}","starred_url":"https://api.github.com/users/aitoralmeida/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aitoralmeida/subscriptions","organizations_url":"https://api.github.com/users/aitoralmeida/orgs","repos_url":"https://api.github.com/users/aitoralmeida/repos","events_url":"https://api.github.com/users/aitoralmeida/events{/privacy}","received_events_url":"https://api.github.com/users/aitoralmeida/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/aitoralmeida/networkx","description":"Official NetworkX source code repository.  ","fork":true,"url":"https://api.github.com/repos/aitoralmeida/networkx","forks_url":"https://api.github.com/repos/aitoralmeida/networkx/forks","keys_url":"https://api.github.com/repos/aitoralmeida/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/aitoralmeida/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/aitoralmeida/networkx/teams","hooks_url":"https://api.github.com/repos/aitoralmeida/networkx/hooks","issue_events_url":"https://api.github.com/repos/aitoralmeida/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/aitoralmeida/networkx/events","assignees_url":"https://api.github.com/repos/aitoralmeida/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/aitoralmeida/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/aitoralmeida/networkx/tags","blobs_url":"https://api.github.com/repos/aitoralmeida/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/aitoralmeida/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/aitoralmeida/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/aitoralmeida/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/aitoralmeida/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/aitoralmeida/networkx/languages","stargazers_url":"https://api.github.com/repos/aitoralmeida/networkx/stargazers","contributors_url":"https://api.github.com/repos/aitoralmeida/networkx/contributors","subscribers_url":"https://api.github.com/repos/aitoralmeida/networkx/subscribers","subscription_url":"https://api.github.com/repos/aitoralmeida/networkx/subscription","commits_url":"https://api.github.com/repos/aitoralmeida/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/aitoralmeida/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/aitoralmeida/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/aitoralmeida/networkx/issues/comments{/number}","contents_url":"https://api.github.com/repos/aitoralmeida/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/aitoralmeida/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/aitoralmeida/networkx/merges","archive_url":"https://api.github.com/repos/aitoralmeida/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/aitoralmeida/networkx/downloads","issues_url":"https://api.github.com/repos/aitoralmeida/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/aitoralmeida/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/aitoralmeida/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/aitoralmeida/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/aitoralmeida/networkx/labels{/name}","releases_url":"https://api.github.com/repos/aitoralmeida/networkx/releases{/id}","created_at":"2014-10-02T12:02:32Z","updated_at":"2014-09-30T05:46:22Z","pushed_at":"2015-07-01T09:58:46Z","git_url":"git://github.com/aitoralmeida/networkx.git","ssh_url":"git@github.com:aitoralmeida/networkx.git","clone_url":"https://github.com/aitoralmeida/networkx.git","svn_url":"https://github.com/aitoralmeida/networkx","homepage":"http://networkx.github.io","size":12319,"stargazers_count":0,"watchers_count":0,"language":null,"has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"networkx:master","ref":"master","sha":"7afdcdcb2c4e98a48bc35fd9a195a56487a2ac09","user":{"login":"networkx","id":388785,"avatar_url":"https://avatars.githubusercontent.com/u/388785?v=3","gravatar_id":"","url":"https://api.github.com/users/networkx","html_url":"https://github.com/networkx","followers_url":"https://api.github.com/users/networkx/followers","following_url":"https://api.github.com/users/networkx/following{/other_user}","gists_url":"https://api.github.com/users/networkx/gists{/gist_id}","starred_url":"https://api.github.com/users/networkx/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/networkx/subscriptions","organizations_url":"https://api.github.com/users/networkx/orgs","repos_url":"https://api.github.com/users/networkx/repos","events_url":"https://api.github.com/users/networkx/events{/privacy}","received_events_url":"https://api.github.com/users/networkx/received_events","type":"Organization","site_admin":false},"repo":{"id":890377,"name":"networkx","full_name":"networkx/networkx","owner":{"login":"networkx","id":388785,"avatar_url":"https://avatars.githubusercontent.com/u/388785?v=3","gravatar_id":"","url":"https://api.github.com/users/networkx","html_url":"https://github.com/networkx","followers_url":"https://api.github.com/users/networkx/followers","following_url":"https://api.github.com/users/networkx/following{/other_user}","gists_url":"https://api.github.com/users/networkx/gists{/gist_id}","starred_url":"https://api.github.com/users/networkx/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/networkx/subscriptions","organizations_url":"https://api.github.com/users/networkx/orgs","repos_url":"https://api.github.com/users/networkx/repos","events_url":"https://api.github.com/users/networkx/events{/privacy}","received_events_url":"https://api.github.com/users/networkx/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/networkx/networkx","description":"Official NetworkX source code repository.  ","fork":false,"url":"https://api.github.com/repos/networkx/networkx","forks_url":"https://api.github.com/repos/networkx/networkx/forks","keys_url":"https://api.github.com/repos/networkx/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/networkx/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/networkx/networkx/teams","hooks_url":"https://api.github.com/repos/networkx/networkx/hooks","issue_events_url":"https://api.github.com/repos/networkx/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/networkx/networkx/events","assignees_url":"https://api.github.com/repos/networkx/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/networkx/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/networkx/networkx/tags","blobs_url":"https://api.github.com/repos/networkx/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/networkx/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/networkx/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/networkx/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/networkx/networkx/languages","stargazers_url":"https://api.github.com/repos/networkx/networkx/stargazers","contributors_url":"https://api.github.com/repos/networkx/networkx/contributors","subscribers_url":"https://api.github.com/repos/networkx/networkx/subscribers","subscription_url":"https://api.github.com/repos/networkx/networkx/subscription","commits_url":"https://api.github.com/repos/networkx/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/networkx/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/networkx/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/networkx/networkx/issues/comments{/number}","contents_url":"https://api.github.com/repos/networkx/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/networkx/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/networkx/networkx/merges","archive_url":"https://api.github.com/repos/networkx/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/networkx/networkx/downloads","issues_url":"https://api.github.com/repos/networkx/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/networkx/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/networkx/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/networkx/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/networkx/networkx/labels{/name}","releases_url":"https://api.github.com/repos/networkx/networkx/releases{/id}","created_at":"2010-09-06T00:53:44Z","updated_at":"2015-07-30T10:08:50Z","pushed_at":"2015-07-30T06:33:19Z","git_url":"git://github.com/networkx/networkx.git","ssh_url":"git@github.com:networkx/networkx.git","clone_url":"https://github.com/networkx/networkx.git","svn_url":"https://github.com/networkx/networkx","homepage":"http://networkx.github.io","size":22992,"stargazers_count":1509,"watchers_count":1509,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":490,"mirror_url":null,"open_issues_count":249,"forks":490,"open_issues":249,"watchers":1509,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1560"},"html":{"href":"https://github.com/networkx/networkx/pull/1560"},"issue":{"href":"https://api.github.com/repos/networkx/networkx/issues/1560"},"comments":{"href":"https://api.github.com/repos/networkx/networkx/issues/1560/comments"},"review_comments":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1560/comments"},"review_comment":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1560/commits"},"statuses":{"href":"https://api.github.com/repos/networkx/networkx/statuses/29d330533e2987b57264fe61341a12ce7b12f388"}}}}