Community Detection in Collaborative Tagging Systems - Community-Built Databases: Research and Development - page 119

5.3.2 Community Expansion

Starting from a community seed set S , the second step in the proposed community
detection method involves an expansion process, which aims at attaching additional
nodes, which are relevant, to the initial community seed set. The expansion step is
essential for deriving higher quality communities since the community seed sets
produced by the previous step may fail to include in the communities nodes that are
of importance for them. In the case of tag communities, this would lead to tag
communities that would miss some important keywords and would thus be less
representative of their topic. In addition, it is due to this expansion step that overlap
among communities is possible since the previous step produces non-overlapping
community seed sets.
The community expansion step is based on the maximization of a local measure
of community quality, namely subgraph modularity introduced in [ 33 ]. The mod-
ularity of a subgraph S V is defined as the ratio of the number of intra-community

edges (edges connecting nodes within S ) over the number of edges sticking out of
S (5.5). Obviously, the larger such a value is, the more well separated the subgraph
is from the rest of the graph. In the extreme case of a disconnected subgraph, its
modularity value tends to infinity:

∈

jfð v ; w Þ2 E j v ; w 2 S gj

M ð S Þ¼ (5.5)

jfð v ; w Þ2 E j v 2 S ^ w 2 V S gj

The proposed expansion step is based on a greedy maximization scheme, i.e., it
successively attaches nodes to community S as long as their addition increases the
subgraph modularity M ( S ) of the community. The set of nodes that are considered
as candidates for attachment to S are pooled from the “community frontier,” i.e., the
set of all nodes that are adjacent to at least one node of the community. Each
candidate node is tentatively attached to the community and the new value of
its modularity is computed. Nodes with very high degree 6 are not considered in
this process for two reasons: (a) to reduce the computational complexity of the
expansion step and (b) to prevent the expansion process from creating a “gigantic”
community. The node resulting in the maximum increase of modularity for the
community is considered a member of the community and the process is repeated
for the rest of the candidate nodes (it is possible that there is no increase of modu-
larity by adding a node to the community, in which case no expansion takes place).
The expansion process is specified in Algorithm 1 and exemplified in Fig. 5.4a, b .It
is thanks to this expansion step that overlap among the resulting communities is
possible.

6 We create a degree-ordered list of nodes for the whole graph and consider as high-degree nodes
the top 10% of them.