کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
534020 870206 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dense subgraph mining with a mixed graph model
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر چشم انداز کامپیوتر و تشخیص الگو
پیش نمایش صفحه اول مقاله
Dense subgraph mining with a mixed graph model
چکیده انگلیسی


• Three-phase method using standard and bipartite graphs for finding dense clusters.
• The first step is a seed mining phase in the standard graph model followed by a seed refining phase in both graph models.
• The third phase is a clustering in the bipartite graph.
• Finding overlapping clusters and handling outliers without degree restrictions.
• New lemma and proof on density bounds of bipartite subgraphs.

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Pattern Recognition Letters - Volume 34, Issue 11, 1 August 2013, Pages 1252–1262
نویسندگان
, , ,