Script pour obtenir une animation de la toile de confiance duniter. [dépôt archivé] le code a été intégré à DataJune (https://git.42l.fr/HugoTrentesaux/DataJune.jl)
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This repo is archived. You can view files and clone it, but cannot push or open issues/pull-requests.
 
 
 

123 lines
4.8 KiB

# community detection algorithm inspired by LightGraph.label_propagation
# but adapted for dynamic graph
module Community
using LightGraphs
"""
label_propagation!(g::AbstractGraph, label::AbstractVector, c::LightGraphs.NeighComm, maxiter=1000)
label_propagation is a modified version of LightGraphs.label_propagation
N is the maximum number of nodes
(!) label is the initial labels of the g nodes (between 1 and N)
(!) c is a counter allocated once before computation (size N), has to be initialized before
"""
function label_propagation!(g::AbstractGraph, label::AbstractVector, counter::LightGraphs.NeighComm, maxiter=1000)
n = nv(g)
n == 0 && return
reset!(counter) # reset counter
active_vs = BitSet(vertices(g)) # set of active nodes (node which community is expected to change)
convergence_hist = Vector{Int}() # keeps track of convergence
random_order = Vector{Int}(undef, n) # used to randomize order (TODO preallocate and use permutation instead?)
i = 0
while !isempty(active_vs) && i < maxiter # while active nodes remain (with a given limit)
num_active = length(active_vs) # counts number of active nodes
push!(convergence_hist, num_active) # record history
i += 1 # next iteration
# process the nodes in random order (TODO investigate the effects)
for (j, node) in enumerate(active_vs)
random_order[j] = node
end
LightGraphs.range_shuffle!(1:num_active, random_order) # https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
# for each active node, check if it's community changes
@inbounds for j = 1:num_active
u = random_order[j]
old_comm = label[u] # old community of node
label[u] = vote!(g, label, counter, u) # get the most represented community in neighbors of u
# (modifies the community counter to avoid allocating new one, but nothing else)
if old_comm != label[u] # if community changed
for v in outneighbors(g, u) # all its neighbor become active again
push!(active_vs, v)
end
else # if community did not change
delete!(active_vs, u) # node stops being active
end
end
end
# print convergence_hist ?
end
"""
vote!(g, m, c, u)
Return the label with greatest frequency. (modified version of LightGraphs.vote! to accept AbstractVector)
# return the label with greatest frequency for node u in graph g
# c is used to track the neighborhood of u
# m is the list of communities for each node u
"""
function vote!(g::AbstractGraph, m::AbstractVector, c::LightGraphs.NeighComm, u::Integer)
# initialize everything to -1 (undefined)
@inbounds for i = 1:c.neigh_last - 1
c.neigh_cnt[c.neigh_pos[i]] = -1
end
c.neigh_last = 1 # number of communities among neighbor +1 (this line is useless)
c.neigh_pos[1] = m[u] # community of community number i (links a number to a community)
c.neigh_cnt[c.neigh_pos[1]] = 0 # count of nodes in each community
c.neigh_last = 2 # after counting node u we will count it's neighbors
max_cnt = 0 # maximal number of neighbors in the same category
for neigh in outneighbors(g, u) # for each outneighbor of u
neigh_comm = m[neigh] # community of neighbor
if c.neigh_cnt[neigh_comm] < 0 # if this community has not been encountered yet
c.neigh_cnt[neigh_comm] = 0 # set it's number to 0 (will be incremented after)
c.neigh_pos[c.neigh_last] = neigh_comm # register this community
c.neigh_last += 1 # increment the number of community
end
c.neigh_cnt[neigh_comm] += 1 # increment neighbor count for this community
if c.neigh_cnt[neigh_comm] > max_cnt # if this community is the most represented
max_cnt = c.neigh_cnt[neigh_comm] # update the max number
end
end
# ties breaking randomly (?)
LightGraphs.range_shuffle!(1:c.neigh_last - 1, c.neigh_pos) # shuffle the link between community number and community (?)
result_lbl = zero(eltype(c.neigh_pos))
# let label change if an other label has the same neighbor count
for lbl in c.neigh_pos # interate over all possible communities
if c.neigh_cnt[lbl] == max_cnt # if this community is as large, update it and break
result_lbl = lbl
break
end
end
# I guess it allows community to fluctuate if the size is the same (for next iteration)
return result_lbl
end
"""
reset NeighComm
"""
function reset!(self::LightGraphs.NeighComm)
N = size(self.neigh_pos,1)
self.neigh_pos .= 1:N
fill!(self.neigh_cnt, -1)
self.neigh_last = 1
end
"""
initialize NeighComm
"""
NeighComm(N::Int) = LightGraphs.NeighComm(collect(1:N), fill(-1, N), 1)
end