Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/25887' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/25887' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Analysis of Dense Partial Coverings of Large Social and information Networks | IIT - CNR - Istituto di Informatica e Telematica
IIT Home Page CNR Home Page

Analysis of Dense Partial Coverings of Large Social and information Networks

Characterizing and detecting dense subgraphs (tight communities) of social graphs is an important exploratory tool in social network analysis. Several approaches have been proposed that either (i) partition the whole network into "clusters", even in low density region, or (ii) are aimed at finding a single dense community (an need to be iterated to find the next one). As social networks grow larger both apporaches (i) and (ii) result in algorithms too slow to be practical, in particular when on-the-fly results are needed. In this paper we propose an alternative approach that aims at balancing efficiency of computation and expressiveness/manageability of the output community representation. We define the notion of a partial dense cover (PDC) of a graph. Intutively a PDC of a graph is that set of nodes that (a) forma set of disjoint dense induced subgraphs and (b) whose removal leaves the residual graph without dense regions. Exact computation of PDC is an NP-complete problem. Thus, we propose efficient heuristic algorithms for computing them. Precision and recall of the approach is measured by embedding dense subgraphs in large social networks and by measuring the ability of our method in finding them blindly


2012

Autori esterni: Emilio Lastres (SISTER, Sistemi Territoriali )
Autori IIT:

Miriam Baglioni

Foto di Miriam Baglioni

Tipo: TR Rapporti tecnici
Area di disciplina: Mathematics
IIT TR-01/2012

File: TR-01-2012.pdf