Database Reference
In-Depth Information
Tag roles . Most existing community detection methods treat network nodes in a
uniform way. In the case of tag networks, however, this may lead to poor results. For
instance, tags that are used by many users tend to denote generic topics (categories)
that are connected to a large number of different tags. Unless such tags are treated in
a special way by community agglomeration or expansion schemes, it is possible that
topically irrelevant terms will end up in the same community due to their transitive
relation through some generic tag. Thus, a community detection approach, which
differentiates between generic and regular tags, is more likely to yield meaningful
tag communities.
Importance of local context . The majority of existing clustering and community
detection schemes requires access to the complete network structure in order to
perform the division of nodes into communities. Such a global approach has two
undesired implications. First, it incurs substantial amounts of recalculations to
derive the updated community structure after changes take place on a network,
even when these changes are only minor. This renders global approaches computa-
tionally inefficient and thus limits their applicability to static snapshots of networks.
Such a limitation diminishes their utility in the context of Collaborative Tagging
Systems since these systems are massive and highly dynamic. A second implication
of the global approach in community detection is the effect of total network scale on
the size of communities that are detectable: it was found in [ 32 ] that even profound
communities are not discovered by modularity maximization algorithms if their
size falls below some threshold that is dependent on the network scale.
In order to address the aforementioned particularities of tag networks, we intro-
duced in [ 16 ] a hybrid community detection scheme based on two steps: (a) com-
munity seed set detection based on the notion of (
)-cores (Sect. 5.3.1 ) and (b) local
expansion of the identified cores with the goal of attaching additional relevant nodes
(Sect. 5.3.2 ). While the proposed combined approach successfully tackles the
specific requirements of tag networks, it is also troubled by the need to set para-
meters, specifically, two parameters (
m
,
e
) for the community seed set selection
and an additional parameter ( B L ) for the local community expansion step. For this
reason, we introduced in [ 17 ] a parameter-free refinement of the community detec-
tion scheme of [ 16 ], which we describe in the following.
m
and
e
5.3.1 Community Seed Set Detection
The community seed set detection step of our method is based on the concept of
(
m
,
e
)-cores introduced in [ 4 ]. The definition of (
m
,
e
)-cores is based on the concepts
of structural similarity and
-neighborhood that we repeat here for convenience. We
also repeat the definition of direct structure reachability.
e
Definition 2. The structural similarity between two nodes v and w of a graph
G
¼
{V, E} is defined as:
Þ¼ j G ð
Þj
j G ð
v
Þ\ G ð
w
p
v
;
w
(5.1)
v
Þj j G ð
w
Þj
Search WWH ::




Custom Search