Parts | Days | Selection | Search | Downloads | Help
DY: Fachverband Dynamik und Statistische Physik
DY 4: Statistical physics of complex networks I
DY 4.1: Talk
Monday, March 26, 2007, 12:00–12:15, H3
Ranking and Community detection in unweighted networks — •Andrea Baldassarri1, Ciro Cattuto1,2, Vito Servedio1,2, Vittorio Loreto1, Miranda Grahl3, Andreas Hotho3, Christoph Schmitz3, and Gerd Stumme3 — 1Dipartimento di Fisica, Università La Sapienza, P.le A. Moro 2, 00185 Roma, Italy — 2Museo Storico della Fisica e Centro Studi e Ricerche Enrico Fermi, Compendio Viminale, 00184 Rome, Italy — 3Knowledge & Data Engineering Group, University of Kassel, Wilhelmshöher Allee 73, 34121 Kassel, Germany
Networks are a way to encode relational informations between many interacting entities (nodes). This information can be used in different ways in order to capture relevant features of the system. Site ranking algorithms, as for instance the PageRank algorithm, use topological informations embedded in a directed network to infer the relative importance of nodes. Recently, we introduced a ranking procedure, the FolkRank algirthm, for a new class of social annotation networks, so-called folksonomies. Differently to PageRank, it allows for undirected networks.
On the other hand, community detection algorithms try to detect relation similarities at a higher level. An example is the Markov Clustering algorithm (MCL), in which a renormalization-like scheme is used in order to detect communities of nodes in weighted networks.
In this paper, we will analyse the commonalities ot the two approaches. In particular we identify the relationship between ranking and community building in folksonomies.