[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Qualifying individual communities
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Qualifying individual communities |
Date: |
Wed, 5 Feb 2014 10:44:04 +0100 |
> What confused me was the description of the membership function, namely for
> hierarchical algorithms like infomap:
infomap is not hierarchical as far as I know; edge.betweenness.community,
fastgreedy.community and walktrap.community are hierarchical for sure. Infomap
gives you a single partition only.
> "membership gives the division of the vertices, into communities. It returns
> a numeric vector, one value for each vertex, the id of its community.
> Community ids start from one. Note that some algorithms calculate the
> complete (or incomplete) hierarchical structure of the communities, and not
> just a single partitioning. For these algorithms typically the membership for
> the highest modularity value is returned, but see also the manual pages of
> the individual algorithms."
>
> This implies there are multiple modularity values used not only to nest the
> clusters but to measure their individual modularity to construct a dendrogram.
Hierarchical algorithms give you a full dendrogram which is either built from
the bottom up (i.e. the algorithm merges nodes or communities progressively
until it is left with a single community only) or from the top down (i.e. the
algorithm splits communities progressively until each node is separated into
its own community). Either way, the dendrogram is essentially a sequence of
merges or splits that one can perform on the nodes of the graph in order to
derive communities. In this case, igraph has to find a way to determine where
to “cut” the dendrogram (i.e. stop the splitting or merging), and it uses the
modularity measure to decide that; basically it calculates the modularity of
the current partition, then performs the next merge from the dendrogram,
calculates the modularity again, and so on. Then it selects the partitioning
that yielded the highest possible modularity.
T.