Atzmueller, M.; Doerfel, S. & Mitzlaff, F. (2015), 'Description-oriented community detection using exhaustive subgroup discovery ', Information Sciences (0) , - .
[BibTeX] [Endnote]

Abstract Communities can intuitively be defined as subsets of nodes of a graph with a dense structure in the corresponding subgraph. However, for mining such communities usually only structural aspects are taken into account. Typically, no concise nor easily interpretable community description is provided. For tackling this issue, this paper focuses on description-oriented community detection using subgroup discovery. In order to provide both structurally valid and interpretable communities we utilize the graph structure as well as additional descriptive features of the graph’s nodes. A descriptive community pattern built upon these features then describes and identifies a community, i.e., a set of nodes, and vice versa. Essentially, we mine patterns in the “description space” characterizing interesting sets of nodes (i.e., subgroups) in the “graph space”; the interestingness of a community is evaluated by a selectable quality measure. We aim at identifying communities according to standard community quality measures, while providing characteristic descriptions of these communities at the same time. For this task, we propose several optimistic estimates of standard community quality functions to be used for efficient pruning of the search space in an exhaustive branch-and-bound algorithm. We demonstrate our approach in an evaluation using five real-world data sets, obtained from three different social media applications.

Ke, Q. & Ahn, Y.-Y. (2014), 'Tie strength distribution in scientific collaboration networks', Phys. Rev. E 90 (3) , 032804 .
[BibTeX] [Endnote]

2013

Kibanov, M.; Atzmueller, M.; Scholz, C. & Stumme, G. (2013), On the Evolution of Contacts and Communities in Networks of Face-to-Face Proximity, in 'Proc. IEEE CPSCom 2013' , IEEE Computer Society, Boston, MA, USA .
[BibTeX] [Endnote]

Mitzlaff, F.; Atzmueller, M.; Benz, D.; Hotho, A. & Stumme, G. (2013), 'User-Relatedness and Community Structure in Social Interaction Networks' , cite arxiv:1309.3888 .
[BibTeX] [Endnote]

With social media and the according social and ubiquitous applications finding their way into everyday life, there is a rapidly growing amount of user generated content yielding explicit and implicit network structures. We consider social activities and phenomena as proxies for user relatedness. Such activities are represented in so-called social interaction networks or evidence networks, with different degrees of explicitness. We focus on evidence networks containing relations on users, which are represented by connections between individual nodes. Explicit interaction networks are then created by specific user actions, for example, when building a friend network. On the other hand, more implicit networks capture user traces or evidences of user actions as observed in Web portals, blogs, resource sharing systems, and many other social services. These implicit networks can be applied for a broad range of analysis methods instead of using expensive gold-standard information. In this paper, we analyze different properties of a set of networks in social media. We show that there are dependencies and correlations between the networks. These allow for drawing reciprocal conclusions concerning pairs of networks, based on the assessment of structural correlations and ranking interchangeability. Additionally, we show how these inter-network correlations can be used for assessing the results of structural analysis techniques, e.g., community mining methods.

2012

Atzmueller, M.; Doerfel, S.; Hotho, A.; Mitzlaff, F. & Stumme, G. (2012), Face-to-Face Contacts at a Conference: Dynamics of Communities and Roles 'Modeling and Mining Ubiquitous Social Media' , Springer Verlag, Heidelberg, Germany .
[BibTeX] [Endnote]

Atzmueller, M. (2012), 'Mining Social Media', Informatik Spektrum 35 (2) , 132-135 .
[BibTeX] [Endnote]

Atzmueller, M. (2012), 'Mining Social Media: Key Players, Sentiments, and Communities', WIREs: Data Mining and Knowledge Discovery In Press .
[BibTeX] [Endnote]

Doerfel, S.; Jäschke, R. & Stumme, G. (2012), Publication Analysis of the Formal Concept Analysis Community, in F. Domenach; D.I. Ignatov & J. Poelmans, ed., 'ICFCA 2012' , Springer, Berlin/Heidelberg , pp. 77--95 .
[BibTeX] [Endnote]

Doerfel, S.; Jäschke, R. & Stumme, G. (2012), Publication Analysis of the Formal Concept Analysis Community, in F. Domenach; D.I. Ignatov & J. Poelmans, ed., 'Formal Concept Analysis' , Springer, Berlin/Heidelberg , pp. 77--95 .
[BibTeX] [Endnote]

Hristova, D.; Mashhadi, A.; Quattrone, G. & Capra, L. (2012), Mapping Community Engagement with Urban Crowd-Sourcing, in 'Proc. When the City Meets the Citizen Workshop (WCMCW)' .
[BibTeX] [Endnote]

Communities of people are better mappers if they are spatially clustered, as revealed in an interesting new paper by Hristova, Mashhadi, Quattrone and Capra from UCL. "This preliminary analysis inspires further inquiry because it shows a clear correlation between spatial afﬁliation, the internal community structure and the community’s engagement in terms of coverage", according to the authors. They have studied the similarity patterns among eight hundred contributors to OpenStreetMap, the well-known crowdmapping project and detected the hidden community structure. It is a very promising field of research, coupling a social network analysis of crowdsourced data. Participants to such projects are rarely independent individuals: in most cases, they involve communities more than single participants and it would be crucial to uncover how the underlying social structure reflects on the quantity and the quality of the collected data. It has the greatest relevance for citizen science projects, as data quality is often the key issue determining the success or the failure of the collective effort.

2011

Giatsidis, C.; Thilikos, D. M. & Vazirgiannis, M. (2011), Evaluating Cooperation in Communities with the k-Core Structure, in 'Advances in Social Networks Analysis and Mining (ASONAM), 2011 International Conference on' , pp. 87-93 .
[BibTeX] [Endnote]

Community sub graphs are characterized by dense connections or interactions among its nodes. Community detection and evaluation is an important task in graph mining. A variety of measures have been proposed to evaluate the quality of such communities. In this paper, we evaluate communities based on the k-core concept, as means of evaluating their collaborative nature - a property not captured by the single node metrics or by the established community evaluation metrics. Based on the k-core, which essentially measures the robustness of a community under degeneracy, we extend it to weighted graphs, devising a novel concept of k-cores on weighted graphs. We applied the k-core approach on large real world graphs - such as DBLP and report interesting results.

Mitzlaff, F.; Atzmueller, M.; Benz, D.; Hotho, A. & Stumme, G. (2011), Community Assessment Using Evidence Networks, in Martin Atzmueller; Andreas Hotho; Markus Strohmaier & Alvin Chin, ed., 'Analysis of Social Media and Ubiquitous Data' , Springer Berlin Heidelberg, , pp. 79-98 .
[BibTeX] [Endnote]

Zhang, D.; Guo, B. & Yu, Z. (2011), 'The Emergence of Social and Community Intelligence', Computer 44 (7) , 21--28 .
[BibTeX] [Endnote]

2010

Fortunato, S. (2010), 'Community detection in graphs ', Physics Reports 486 (3–5) , 75 - 174 .
[BibTeX] [Endnote]

The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.

Mucha, P. J.; Richardson, T.; Macon, K.; Porter, M. A. & Onnela, J.-P. (2010), 'Community Structure in Time-Dependent, Multiscale, and Multiplex Networks', Science 328 (5980) , 876-878 .
[BibTeX] [Endnote]

Network science is an interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. A prominent problem in network science is the algorithmic detection of tightly connected groups of nodes known as communities. We developed a generalized framework of network quality functions that allowed us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through links that connect each node in one network slice to itself in other slices. This framework allows studies of community structure in a general setting encompassing networks that evolve over time, have multiple types of links (multiplexity), and have multiple scales.

2005

Binder, M.; Hibbett, D. S.; Larsson, K. H.; Larsson, E.; Langer, E. & Langer, G. (2005), 'The phylogenetic distribution of resupinate forms across the major clades of mushroom-forming fungi (Homobasidiomycetes)', Systematics and Biodiversity 3 (2) , 113-157 .
[BibTeX] [Endnote]

Phylogenetic relationships of resupinate Homobasidiomycetes (Corticiaceae s. lat. and others) were studied using ribosomal DNA (rDNA) sequences from a broad sample of resupinate and nonresupinate taxa. Two datasets were analysed using parsimony, a'core'dataset of 142 species, each of which is represented by four rDNA regions (mitochondrial and nuclear large and small subunits), and a 'full' clataset of 656 species, most of which were represented only by nuclear large subunit rDNA sequences. Both datasets were analysed using traditional heuristic methods with bootstrapping, and the full clataset was also analysed with the Parsimony Ratchet, using equal character weights and six-parameter weighted parsimony. Analyses of both datasets supported monophyly of the eight major clades of Homobasicliomycetes recognised by Hibbett and Thorn, as well as independent lineages corresponding to the Gloeophyllum clade, corticioid clade and jaapia argillacea. Analyses of the full clataset resolved two additional groups, the athelioid clade and trechisporoid clade (the latter may be nested in the polyporoid clade). Thus, there are at least 12 independent clades of Homobasicliomycetes. Higher-level relationships among the major clades are not resolved with confidence. Nevertheless, the euagarics clade, bolete clade, athelioid clade and jaapia argillacea are consistently resolved as a monophyletic group, whereas the cantharelloid clade, gomphoid-phalloid clade and hymenochaetoid clade are placed at the base of the Homobasidiomycetes, which is consistent with the preponderance of imperforate parenthesomes in those groups. Resupinate forms occur in each of the major clades of Homobasidiomycetes, some of which are composed mostly or exclusively of resupinate forms (athelioid clade, corticioid clade, trechisporoid clade,jaapia). The largest concentrations of resupinate forms occur in the polyporoid clade, russuloid clade and hymenochaetoid clade. The cantharelloid clade also includes many resupinate forms, including some that have traditionally been regarded as heterobasidiomycetes (Sebacinaceae, Tulasnellates, Ceratobasidiales). The euagarics clade, which is by far the largest clade in the Homobasidiomycetes, has the smallest fraction of resupinate species. Results of the present study are compared with recent phylogenetic analyses, and a table summarising the phylogenetic distribution of resupinate taxa is presented, as well as notes on the ecology of resupinate forms and related Homobasidiomycetes.

2004

Newman, M. E. J. & Girvan, M. (2004), 'Finding and evaluating community structure in networks', Phys. Rev. E 69 (2) , 026113 .
[BibTeX] [Endnote]

2000

Yu, B. & Singh, M. (2000), A Social Mechanism of Reputation Management in Electronic Communities, in Matthias Klusch & Larry Kerschberg, ed., 'Cooperative Information Agents IV - The Future of Information Agents in Cyberspace' , Springer, Berlin/Heidelberg , pp. 355--393 .
[BibTeX] [Endnote]

Trust is important wherever agents must interact. We consider the important case of interactions in electronic communities, where the agents assist and represent principal entities, such as people and businesses. We propose a social mechanism of reputation management, which aims at avoiding interaction with undesirable participants. Social mechanisms complement hard security techniques (such as passwords and digital certificates), which only guarantee that a party is authenticated and authorized, but do not ensure that it exercises its authorization in a way that is desirable to others. Social mechanisms are even more important when trusted third parties are not available. Our specific approach to reputation management leads to a decentralized society in which agents help each other weed out undesirable players.