کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10480299 932648 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A general view on computing communities
ترجمه فارسی عنوان
یک دید کلی در محاسبات جوامع
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
چکیده انگلیسی
We define a community structure of a graph as a partition of the vertices into at least two sets with the property that each vertex has connections to relatively many vertices in its own set compared to any other set in the partition and refer to the sets in such a partition as communities. We show that it is NP-hard to compute a community containing a given set of vertices. On the other hand, we show how to compute a community structure in polynomial time for any connected graph containing at least four vertices except the star graph Sn. Finally, we generalize our results and formally show that counterintuitive aspects are unavoidable for any definition of a community structure with a polynomial time algorithm for computing communities containing specific vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Mathematical Social Sciences - Volume 66, Issue 3, November 2013, Pages 331-336
نویسندگان
,