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

modularity, for example, the greedy modularity optimization technique in [ 31 ]
identifies community structure in a sparse network of n nodes in time O ( n log 2 n ),

which addresses the second of the aforementioned problems. However, classical
modularity optimization approaches also suffer from some weaknesses, such as
inability to find overlapping communities or flat treatment of tags irrespective of
their role in the network (these will be discussed in more detail in Sect. 5.3 ), which
are pertinent in the context of tag community identification. For this reason, we
introduced two density-based community detection methods in [ 16 ] that attempt to
mitigate these weaknesses.

5.2.5 Applications of Community Detection

The results of community detection are valuable for understanding the structure and
dynamics of Collaborative Tagging Systems. The complexity and magnitude of the
microscopic structure of folksonomy networks obfuscate the understanding of
interactions and processes taking place in such systems. Thus, community structure
is necessary since it provides a mesoscopic view on the elements (users, resources,
tags) that constitute the folksonomy, as well as their relations. It is common to
derive community-based views of networks, i.e., networks of which the nodes
correspond to the identified communities of the original networks and the edges
to the relations between the communities (inter-community edges of the original
network are merged and intra-community edges are removed from the view). Such
views are more succinct and informative than the original networks.
Furthermore, communities are a meaningful unit of organization, which means
that their members share a similar role in the system and can thus be treated in the
same way. For that reason, many data analysis tasks and derivative services can
benefit from having access to the knowledge of the network community structure.
For instance, assuming that two users of an online social network are found to
belong to the same community, while there is no explicit link to each other, the
system can recommend them to establish such a link (the so-called “friend recom-
mendation” feature found in many online social networks). In a similar way, if two
pieces of content (e.g., web pages) have been found to belong to the same commu-
nity, then the system can recommend to users who liked the first piece of content to
also read the second (in case they have not done already). It is for this reason that
community detection has found applications in the field of recommendation sys-
tems [ 10 , 13 , 18 , 22 ].
Community structure can be also used as a new means of representing user
profiles [ 12 , 15 ]. In the absence of communities, a user profile could be represented
either as a tag frequency vector in the tag vector space (denoting the number of
times that the given user has used each tag) or as a resource vector (denoting which
resources the user has liked). Due to the sparsity of these vector spaces, this raw
user profile representation is ineffective. For instance, if a user makes frequent use
of the tag “ubuntu,” but not of the tag “Linux,” then it appears as if he/she is not