=Paper=
{{Paper
|id=Vol-1458/E01_CRC33_Atzmueller
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1458/E01_CRC33_Atzmueller.pdf
|volume=Vol-1458
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-1458/E01_CRC33_Atzmueller.pdf</pdf>
<pre>
      Fast Description-Oriented Community Detection
                 using Subgroup Discovery
                                          (Abstract)


                Martin Atzmueller, Stephan Doerfel, and Folke Mitzlaff

                   University of Kassel, ITeG Research Center, KDE Group
                      Wilhelmshöher Allee 73, 34121 Kassel, Germany
            {atzmueller, doerfel, mitzlaff}@cs.uni-kassel.de



Abstract
Communities can intuitively be defined as subsets of nodes of a graph with a dense
structure. However, for mining such communities usually only structural aspects are
taken into account. Typically, no concise and easily interpretable community descrip-
tion is provided. For tackling this issue, we focus on fast description-oriented commu-
nity detection using subgroup discovery, cf. [1, 2]. In order to provide both structurally
valid and interpretable communities we utilize the graph structure as well as additional
descriptive features of the contained nodes. A descriptive community pattern built upon
these features then describes and identifies a community given by a set of nodes, and
vice versa. Essentially, we mine for patterns in the “description space” characterizing
interesting sets of nodes in the “graph/community space”; the interestingness of a com-
munity is then evaluated by a selectable quality measure.
    We aim at identifying communities according to standard community quality mea-
sures, while providing characteristic descriptions of the respective communities at the
same time. In order to implement an efficient approach, we propose several optimistic
estimates of standard community quality functions. Together with the proposed exhaus-
tive branch-and-bound algorithm, these estimates enable fast description-oriented com-
munity detection. This is demonstrated in an evaluation using five real-world data sets,
obtained from three different social media applications.

References
1. Atzmueller, M., Doerfel, S., Mitzlaff, F.: Description-Oriented Community De-
   tection using Exhaustive Subgroup Discovery. Information Sciences (2015),
   http://dx.doi.org/10.1016/j.ins.2015.05.008
2. Atzmueller, M., Mitzlaff, F.: Efficient Descriptive Community Mining. In: Proc. 24th Interna-
   tional FLAIRS Conference. pp. 459 – 464. AAAI Press, Palo Alto, CA, USA (2011)

  This abstract summarizes the paper [1].
  Copyright c 2015 by the paper’s authors. Copying permitted only for private and academic
  purposes. In: R. Bergmann, S. Görg, G. Müller (Eds.): Proceedings of the LWA 2015 Work-
  shops: KDML, FGWM, IR, and FGDB. Trier, Germany, 7.-9. October 2015, published at
  http://ceur-ws.org




                                              51

</pre>