{"action":"created","comment":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments/46578235","id":46578235,"diff_hunk":"@@ -0,0 +1,83 @@\n+\"\"\"\n+Community detection using the label propagation algorithm (see [Raghavan et al.](http://arxiv.org/abs/0709.2938)).\n+`g`: imput Graph\n+`ϵ`: proportion of unsatisfied nodes\n+return : array containing vertex assignments\n+\"\"\"\n+function label_propagation(g::SimpleGraph, ϵ=1.0e-8)\n+    n = nv(g)\n+    label = collect(1:n)\n+    runing_nodes = Set(vertices(g))\n+\n+    while length(runing_nodes) > n*ϵ\n+        order = shuffle(collect(runing_nodes))\n+        for u in order\n+            if update_label!(g, label, u)\n+                for v in out_neighbors(g, u)\n+                    push!(runing_nodes, v)\n+                end\n+            else\n+                delete!(runing_nodes, u)\n+            end\n+        end\n+    end\n+    permute_labels!(label)\n+\tlabel","path":"src/community/label_propagation.jl","position":25,"original_position":25,"commit_id":"9b1ffc468203164d02ffff58dfb143f60caf8477","original_commit_id":"9b1ffc468203164d02ffff58dfb143f60caf8477","user":{"login":"sbromberger","id":941359,"avatar_url":"https://avatars.githubusercontent.com/u/941359?v=3","gravatar_id":"","url":"https://api.github.com/users/sbromberger","html_url":"https://github.com/sbromberger","followers_url":"https://api.github.com/users/sbromberger/followers","following_url":"https://api.github.com/users/sbromberger/following{/other_user}","gists_url":"https://api.github.com/users/sbromberger/gists{/gist_id}","starred_url":"https://api.github.com/users/sbromberger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sbromberger/subscriptions","organizations_url":"https://api.github.com/users/sbromberger/orgs","repos_url":"https://api.github.com/users/sbromberger/repos","events_url":"https://api.github.com/users/sbromberger/events{/privacy}","received_events_url":"https://api.github.com/users/sbromberger/received_events","type":"User","site_admin":false},"body":"Also, please use explicit `return` statements here. Yes, I'm old-fashioned.","created_at":"2015-12-03T16:56:01Z","updated_at":"2015-12-03T16:56:01Z","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/235#discussion_r46578235","pull_request_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235","_links":{"self":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments/46578235"},"html":{"href":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/235#discussion_r46578235"},"pull_request":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235"}}},"pull_request":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235","id":51249718,"html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/235","diff_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/235.diff","patch_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/235.patch","issue_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/235","number":235,"state":"open","locked":false,"title":"add label propagation algorithm for community detection","user":{"login":"afternone","id":5688019,"avatar_url":"https://avatars.githubusercontent.com/u/5688019?v=3","gravatar_id":"","url":"https://api.github.com/users/afternone","html_url":"https://github.com/afternone","followers_url":"https://api.github.com/users/afternone/followers","following_url":"https://api.github.com/users/afternone/following{/other_user}","gists_url":"https://api.github.com/users/afternone/gists{/gist_id}","starred_url":"https://api.github.com/users/afternone/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/afternone/subscriptions","organizations_url":"https://api.github.com/users/afternone/orgs","repos_url":"https://api.github.com/users/afternone/repos","events_url":"https://api.github.com/users/afternone/events{/privacy}","received_events_url":"https://api.github.com/users/afternone/received_events","type":"User","site_admin":false},"body":"add label_propagation and mutual_information","created_at":"2015-11-19T16:56:35Z","updated_at":"2015-12-03T16:56:01Z","closed_at":null,"merged_at":null,"merge_commit_sha":"63686edfaed0a5a601e5b458f708da996a61394d","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235/commits","review_comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235/comments","review_comment_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments{/number}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/235/comments","statuses_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/statuses/9b1ffc468203164d02ffff58dfb143f60caf8477","head":{"label":"afternone:master","ref":"master","sha":"9b1ffc468203164d02ffff58dfb143f60caf8477","user":{"login":"afternone","id":5688019,"avatar_url":"https://avatars.githubusercontent.com/u/5688019?v=3","gravatar_id":"","url":"https://api.github.com/users/afternone","html_url":"https://github.com/afternone","followers_url":"https://api.github.com/users/afternone/followers","following_url":"https://api.github.com/users/afternone/following{/other_user}","gists_url":"https://api.github.com/users/afternone/gists{/gist_id}","starred_url":"https://api.github.com/users/afternone/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/afternone/subscriptions","organizations_url":"https://api.github.com/users/afternone/orgs","repos_url":"https://api.github.com/users/afternone/repos","events_url":"https://api.github.com/users/afternone/events{/privacy}","received_events_url":"https://api.github.com/users/afternone/received_events","type":"User","site_admin":false},"repo":{"id":46391501,"name":"LightGraphs.jl","full_name":"afternone/LightGraphs.jl","owner":{"login":"afternone","id":5688019,"avatar_url":"https://avatars.githubusercontent.com/u/5688019?v=3","gravatar_id":"","url":"https://api.github.com/users/afternone","html_url":"https://github.com/afternone","followers_url":"https://api.github.com/users/afternone/followers","following_url":"https://api.github.com/users/afternone/following{/other_user}","gists_url":"https://api.github.com/users/afternone/gists{/gist_id}","starred_url":"https://api.github.com/users/afternone/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/afternone/subscriptions","organizations_url":"https://api.github.com/users/afternone/orgs","repos_url":"https://api.github.com/users/afternone/repos","events_url":"https://api.github.com/users/afternone/events{/privacy}","received_events_url":"https://api.github.com/users/afternone/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/afternone/LightGraphs.jl","description":"An optimized graphs package for Julia","fork":true,"url":"https://api.github.com/repos/afternone/LightGraphs.jl","forks_url":"https://api.github.com/repos/afternone/LightGraphs.jl/forks","keys_url":"https://api.github.com/repos/afternone/LightGraphs.jl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/afternone/LightGraphs.jl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/afternone/LightGraphs.jl/teams","hooks_url":"https://api.github.com/repos/afternone/LightGraphs.jl/hooks","issue_events_url":"https://api.github.com/repos/afternone/LightGraphs.jl/issues/events{/number}","events_url":"https://api.github.com/repos/afternone/LightGraphs.jl/events","assignees_url":"https://api.github.com/repos/afternone/LightGraphs.jl/assignees{/user}","branches_url":"https://api.github.com/repos/afternone/LightGraphs.jl/branches{/branch}","tags_url":"https://api.github.com/repos/afternone/LightGraphs.jl/tags","blobs_url":"https://api.github.com/repos/afternone/LightGraphs.jl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/afternone/LightGraphs.jl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/afternone/LightGraphs.jl/git/refs{/sha}","trees_url":"https://api.github.com/repos/afternone/LightGraphs.jl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/afternone/LightGraphs.jl/statuses/{sha}","languages_url":"https://api.github.com/repos/afternone/LightGraphs.jl/languages","stargazers_url":"https://api.github.com/repos/afternone/LightGraphs.jl/stargazers","contributors_url":"https://api.github.com/repos/afternone/LightGraphs.jl/contributors","subscribers_url":"https://api.github.com/repos/afternone/LightGraphs.jl/subscribers","subscription_url":"https://api.github.com/repos/afternone/LightGraphs.jl/subscription","commits_url":"https://api.github.com/repos/afternone/LightGraphs.jl/commits{/sha}","git_commits_url":"https://api.github.com/repos/afternone/LightGraphs.jl/git/commits{/sha}","comments_url":"https://api.github.com/repos/afternone/LightGraphs.jl/comments{/number}","issue_comment_url":"https://api.github.com/repos/afternone/LightGraphs.jl/issues/comments{/number}","contents_url":"https://api.github.com/repos/afternone/LightGraphs.jl/contents/{+path}","compare_url":"https://api.github.com/repos/afternone/LightGraphs.jl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/afternone/LightGraphs.jl/merges","archive_url":"https://api.github.com/repos/afternone/LightGraphs.jl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/afternone/LightGraphs.jl/downloads","issues_url":"https://api.github.com/repos/afternone/LightGraphs.jl/issues{/number}","pulls_url":"https://api.github.com/repos/afternone/LightGraphs.jl/pulls{/number}","milestones_url":"https://api.github.com/repos/afternone/LightGraphs.jl/milestones{/number}","notifications_url":"https://api.github.com/repos/afternone/LightGraphs.jl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/afternone/LightGraphs.jl/labels{/name}","releases_url":"https://api.github.com/repos/afternone/LightGraphs.jl/releases{/id}","created_at":"2015-11-18T03:04:47Z","updated_at":"2015-11-18T03:04:48Z","pushed_at":"2015-12-03T15:17:12Z","git_url":"git://github.com/afternone/LightGraphs.jl.git","ssh_url":"git@github.com:afternone/LightGraphs.jl.git","clone_url":"https://github.com/afternone/LightGraphs.jl.git","svn_url":"https://github.com/afternone/LightGraphs.jl","homepage":"","size":4067,"stargazers_count":0,"watchers_count":0,"language":"Julia","has_issues":false,"has_downloads":true,"has_wiki":false,"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":"JuliaGraphs:master","ref":"master","sha":"df40ce7ee0b71c5b3afa45984e6dcd962ddc0856","user":{"login":"JuliaGraphs","id":10791402,"avatar_url":"https://avatars.githubusercontent.com/u/10791402?v=3","gravatar_id":"","url":"https://api.github.com/users/JuliaGraphs","html_url":"https://github.com/JuliaGraphs","followers_url":"https://api.github.com/users/JuliaGraphs/followers","following_url":"https://api.github.com/users/JuliaGraphs/following{/other_user}","gists_url":"https://api.github.com/users/JuliaGraphs/gists{/gist_id}","starred_url":"https://api.github.com/users/JuliaGraphs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JuliaGraphs/subscriptions","organizations_url":"https://api.github.com/users/JuliaGraphs/orgs","repos_url":"https://api.github.com/users/JuliaGraphs/repos","events_url":"https://api.github.com/users/JuliaGraphs/events{/privacy}","received_events_url":"https://api.github.com/users/JuliaGraphs/received_events","type":"Organization","site_admin":false},"repo":{"id":29314835,"name":"LightGraphs.jl","full_name":"JuliaGraphs/LightGraphs.jl","owner":{"login":"JuliaGraphs","id":10791402,"avatar_url":"https://avatars.githubusercontent.com/u/10791402?v=3","gravatar_id":"","url":"https://api.github.com/users/JuliaGraphs","html_url":"https://github.com/JuliaGraphs","followers_url":"https://api.github.com/users/JuliaGraphs/followers","following_url":"https://api.github.com/users/JuliaGraphs/following{/other_user}","gists_url":"https://api.github.com/users/JuliaGraphs/gists{/gist_id}","starred_url":"https://api.github.com/users/JuliaGraphs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JuliaGraphs/subscriptions","organizations_url":"https://api.github.com/users/JuliaGraphs/orgs","repos_url":"https://api.github.com/users/JuliaGraphs/repos","events_url":"https://api.github.com/users/JuliaGraphs/events{/privacy}","received_events_url":"https://api.github.com/users/JuliaGraphs/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/JuliaGraphs/LightGraphs.jl","description":"An optimized graphs package for Julia","fork":false,"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl","forks_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/forks","keys_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/teams","hooks_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/hooks","issue_events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/events{/number}","events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/events","assignees_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/assignees{/user}","branches_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/branches{/branch}","tags_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/tags","blobs_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/refs{/sha}","trees_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/statuses/{sha}","languages_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/languages","stargazers_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/stargazers","contributors_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/contributors","subscribers_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/subscribers","subscription_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/subscription","commits_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/commits{/sha}","git_commits_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/commits{/sha}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/comments{/number}","issue_comment_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/comments{/number}","contents_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/contents/{+path}","compare_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/merges","archive_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/downloads","issues_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues{/number}","pulls_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls{/number}","milestones_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/milestones{/number}","notifications_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/labels{/name}","releases_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/releases{/id}","created_at":"2015-01-15T19:44:43Z","updated_at":"2015-11-26T17:51:16Z","pushed_at":"2015-12-03T15:17:12Z","git_url":"git://github.com/JuliaGraphs/LightGraphs.jl.git","ssh_url":"git@github.com:JuliaGraphs/LightGraphs.jl.git","clone_url":"https://github.com/JuliaGraphs/LightGraphs.jl.git","svn_url":"https://github.com/JuliaGraphs/LightGraphs.jl","homepage":"","size":4185,"stargazers_count":34,"watchers_count":34,"language":"Julia","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":16,"mirror_url":null,"open_issues_count":17,"forks":16,"open_issues":17,"watchers":34,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235"},"html":{"href":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/235"},"issue":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/235"},"comments":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/235/comments"},"review_comments":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235/comments"},"review_comment":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/235/commits"},"statuses":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/statuses/9b1ffc468203164d02ffff58dfb143f60caf8477"}}}}