Name
Abstract | ||
|---|---|---|
In this paper we introduce a graph clustering method based on dense bipartite subgraph mining. The method applies a mixed graph model (both standard and bipartite) in a three-phase algorithm. First a seed mining method is applied to find seeds of clusters, the second phase consists of refining the seeds, and in the third phase vertices outside the seeds are clustered. The method is able to detect overlapping clusters, can handle outliers and applicable without restrictions on the degrees of vertices or the size of the clusters. The running time of the method is polynomial. A theoretical result is introduced on density bounds of bipartite subgraphs with size and local density conditions. Test results on artificial datasets and social interaction graphs are also presented. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.patrec.2013.03.035 | Pattern Recognition Letters |
Keywords | Field | DocType |
artificial datasets,density bound,social interaction graph,dense bipartite subgraph mining,overlapping cluster,mixed graph model,dense subgraph mining,local density condition,bipartite subgraphs,phase vertex,seed mining method,graph clustering | Complete bipartite graph,Combinatorics,Line graph,Forbidden graph characterization,Graph factorization,Bipartite graph,Factor-critical graph,Mathematics,Subgraph isomorphism problem,Dense graph | Journal |
Volume | Issue | ISSN |
34 | 11 | 0167-8655 |
Citations | PageRank | References |
2 | 0.37 | 29 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anita Keszler | 1 | 9 | 2.17 |
| Tamás Szirányi | 2 | 152 | 26.92 |
| Zsolt Tuza | 3 | 1889 | 262.52 |