A fast and efficient algorithm to identify clusters in networks

Introduction social networks have a strong clustering structure (they contain groups of vertices which are highly interconnected, having many mutual neighbors). Here we consider be synonymous of community, class, module, are also performanc fast algorithms the 0096-3003/$ - see front matter C211 2010 Elsevier Inc. All rights reserved. q Research supported by the Ministerio de Educación y Ciencia, Spain, and the European Regional Development Fund under project TEC2005-03575 and by the Catalan Research Council under project 2005SGR00256. * Corresponding author. E-mail addresses: comellas@ma4.upc.edu (F. Comellas), almirall@ma4.upc.edu (A. Miralles). URL: http://www.ma4.upc.edu/comellas/ (F. Comellas). 1 Avda. Canal Olı ´ mpic s/n, 08860, Castelldefels, Catalonia, Spain. Applied Mathematics and Computation 217

(2010) 2007–2014 Contents lists available at ScienceDirect Applied Mathematics and Computation journal homepage: www.elsevier.com/locate/amc doi:10.1016/j.amc.2010.06.060 to have cluster structure if it consists of subsets of nodes, with many connections among the same subset, but few links between subsets, see, for example [1,2]. Algorithms to detect these subsets have appeared in the literature and they can be classified in two main groups (see the above two references for more details): hierarchical clustering methods (also known as agglomerative), which consist of generating a tree (dendrogram) from a complete graph with as many vertices as the original network and where each edge has a weight measuring how close the corresponding vertices are. Starting from the set of all vertices with no edges between them, edges are iteratively added between pairs of vertices in the order of in social studies, biological (epidemiology systems, cluster computing). Clusters issues for information retrieval. Clusters should be considered to improve their The construction of efficient and a nontrivial task. The first problem is the notion of cluster in a general way. Therefore, depending on the context, it can etc. The problem of detecting clusters in a given network is an important issue , ecological webs, metabolic), and computer science (WWW, Internet, distributed also interesting as they reflect hierarchical aspects and are related to classification play an important role when executing most communication algorithms and e. for the identification of the clustering structure in a generic network is nonexistence of a precise definition of cluster. Intuitively, a network can be said Many real life networks like the WWW, Internet, transportation and communication networks, or even biological and Francesc Comellas * ,1 , Alicia Miralles Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Spain article info Keywords: Graphs Clusters Networks Complex systems abstract A characteristic feature of many relevant real life networks, like the WWW, Internet, trans- portation and communication networks, or even biological and social networks, is their clustering structure. We discuss in this paper a novel algorithm to identify cluster sets of densely interconnected nodes in a network. The algorithm is based on local information and therefore it is very fast with respect other proposed methods, while it keeps a similar performance in detecting the clusters. C211 2010 Elsevier Inc. All rights reserved. decreasing weight. From the tree one can then infer the different clusters. To obtain the weights, some algorithms consider the spectrum of the adjacency...

Website: upcommons.upc.edu | Filesize: -
No of Page(s): 8
Download A fast and efficient algorithm to identify clusters in networks.pdf