direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Detecting Connected Components and Communities in Hypergraphs

From this page you can download the algorithm for decomposing a
3-partite 3-uniform hypergraph stored in a database into its
normal and hyperincident connected components.

hcc.zip

 

If you use this software, please cite:

Hyperincident Connected Components in Tagging Networks
Citation key Neubauer2009a0
Author Neubauer, N. and Obermayer, K.
Pages 229 – 238
Year 2009
DOI http://doi.acm.org/10.1145/1592394.1592398
Journal ACM SIGIWEB Newsletter
Month September
Publisher Association for Computing Machinery
Abstract Data created by social bookmarking systems can be described as 3-partite 3-uniform hypergraphs connecting documents, users, and tags (tagging networks), such that the toolbox of complex network analysis can be applied to examine their properties. One of the most basic tools, the analysis of connected components, however cannot be applied meaningfully: Tagging networks tend to be almost entirely connected. We therefore propose a generalization of connected components, m-hyperincident connected components. We show that decomposing tagging networks into 2-hyperincident connected components yields a characteristic component distribution with a salient giant component that can be found across various datasets. This pattern changes if the underlying formation process changes, for example, if the hypergraph is constructed from search logs, or if the tagging data is contaminated by spam: It turns out that the second- to 129th largest components of the spam-labeled Bibsonomy dataset are inhabited exclusively by spam users. Based on these ndings, we propose and unsupervised method for spam detection.
Bibtex Type of Publication Selected:social
Link to publication Download Bibtex entry

Also, you can download several software packages for
multi-partite community detection in hypergraphs.

mpcd (Multi-Partite Community Detection)

performs community detection based on multi-partite modularity
optimization.

mpcd.zip



mpcb (Multi-Partite Community Benchmarking)

evaluates community detection algorithms based on three different
families of synthetic benchmark hypergraphs.

mpcb.zip, with data: mpcb_with_data.zip




mpce (Multi-Partite Community Exploration)

allows for the interactive exploration of community detection
results such as the ones provided by mpcd.

mpce.zip

 

If you use this software, please cite:

Hyperincident Connected Components in Tagging Networks
Citation key Neubauer2009a0
Author Neubauer, N. and Obermayer, K.
Pages 229 – 238
Year 2009
DOI http://doi.acm.org/10.1145/1592394.1592398
Journal ACM SIGIWEB Newsletter
Month September
Publisher Association for Computing Machinery
Abstract Data created by social bookmarking systems can be described as 3-partite 3-uniform hypergraphs connecting documents, users, and tags (tagging networks), such that the toolbox of complex network analysis can be applied to examine their properties. One of the most basic tools, the analysis of connected components, however cannot be applied meaningfully: Tagging networks tend to be almost entirely connected. We therefore propose a generalization of connected components, m-hyperincident connected components. We show that decomposing tagging networks into 2-hyperincident connected components yields a characteristic component distribution with a salient giant component that can be found across various datasets. This pattern changes if the underlying formation process changes, for example, if the hypergraph is constructed from search logs, or if the tagging data is contaminated by spam: It turns out that the second- to 129th largest components of the spam-labeled Bibsonomy dataset are inhabited exclusively by spam users. Based on these ndings, we propose and unsupervised method for spam detection.
Bibtex Type of Publication Selected:social
Link to publication Download Bibtex entry

For questions and comments, please contact:


Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe