Name
Abstract | ||
|---|---|---|
Abstract We initiate the study of a new clustering framework, called cluster ranking. Rather than simply partitioning a network into clusters, a cluster ranking algorithm also orders the clusters by their strength. To this end, we introduce a novel strength measure for clusters|the integrated cohesion|which is applicable to arbitrary weighted networks. We then present C-Rank: a new cluster ranking algorithm. Given a network with arbitrary pairwise similarity weights, C-Rank creates a list of overlapping clusters and ranks them by their integrated cohesion. We provide extensive theoretical and empirical analysis of C-Rank and show that it is likely to have high precision and recall. A main component,of C-Rank is a heuristic algorithm for flnding sparse vertex separators. At the core of this algorithm is a new connection between the well known measure of vertex betweenness and multicommodity ∞ow. Our experiments focus on mining mailbox networks. A mailbox network is an egocentric social network, consisting of contacts with whom an individual exchanges email. Ties among contacts are represented by the frequency of their co{occurrence on message headers. C-Rank is well suited to mine such networks, since they are abundant with overlapping communities of highly variable strengths. We demonstrate the efiectiveness of C-Rank on the Enron data set, consisting of 130 mailbox networks. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10115-007-0096-0 | Knowledge and Information Systems |
Keywords | DocType | Volume |
clustering · ranking · communities · social networks · social network analysis · graph algorithms,ranking,social network analysis,social network,clustering,social networks,heuristic algorithm | Journal | 14 |
Issue | ISSN | ISBN |
1 | 0219-3116 | 0-7695-2701-9 |
Citations | PageRank | References |
23 | 1.31 | 28 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ziv Bar-Yossef | 1 | 1776 | 118.00 |
| Ido Guy | 2 | 1444 | 85.72 |
| Ronny Lempel | 3 | 1273 | 112.55 |
| Yoëlle S. Maarek | 4 | 361 | 69.41 |
| Vladimir Soroka | 5 | 291 | 27.78 |