Identifying the Presence of Communities in Complex Networks Through Topological Decomposition and Component Densities
Abstract
The exponential growth of data in various fields such as Social Networks
and Internet has stimulated lots of activity in the field of network analysis
and data mining. Identifying Communities remains a fundamental technique to
explore and organize these networks. Few metrics are widely used to discover
the presence of communities in a network. We argue that these metrics do not
truly reflect the presence of communities by presenting counter examples. This
is because these metrics concentrate on local cohesiveness among nodes where
the goal is to judge whether two nodes belong to the same community or vise
versa. Thus loosing the overall perspective of the presence of communities in the
entire network. In this paper, we propose a new metric to identify the presence
of communities in real world networks. This metric is based on the topological
decomposition of networks taking into account two important ingredients of real
world networks, the degree distribution and the density of nodes. We show the
effectiveness of the proposed metric by testing it on various real world data sets