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 findings, we propose and unsupervised method for spam detection.
(private-note)Most interesting part - they suggested to build a different network from tagging network called 2-hyperincident, which connects tagging incidents if they are similar enough. In this network, they found that 2nd to 128th connected component are all spam. So, spam and legitimate links can be separated. However, it looks like this thing can be also found on a normal graphs - user-document. Interesting example of what could be done by link analysis. Maybe, we could use spread-activation and recommendation on this kinds of graphs.
%0 Conference Paper
%1 citeulike:5031993
%A Neubauer, Nicolas
%A Obermayer, Klaus
%B Proceedings of the 20th ACM conference on Hypertext and hypermedia
%C New York, NY, USA
%D 2009
%I ACM
%K best-paper ht09 network-analysis spam tagging
%P 229--238
%R 10.1145/1557914.1557954
%T Hyperincident connected components of tagging networks
%U http://dx.doi.org/10.1145/1557914.1557954
%X 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 findings, we propose and unsupervised method for spam detection.
%@ 978-1-60558-486-7
@inproceedings{citeulike:5031993,
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 findings, we propose and unsupervised method for spam detection.}},
added-at = {2018-03-19T12:24:51.000+0100},
address = {New York, NY, USA},
author = {Neubauer, Nicolas and Obermayer, Klaus},
biburl = {https://www.bibsonomy.org/bibtex/2fa98bda69e12481ea7b79d883f54955d/aho},
booktitle = {Proceedings of the 20th ACM conference on Hypertext and hypermedia},
citeulike-article-id = {5031993},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1557914.1557954},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/1557914.1557954},
comment = {(private-note)Most interesting part - they suggested to build a different network from tagging network called 2-hyperincident, which connects tagging incidents if they are similar enough. In this network, they found that 2nd to 128th connected component are all spam. So, spam and legitimate links can be separated. However, it looks like this thing can be also found on a normal graphs - user-document. Interesting example of what could be done by link analysis. Maybe, we could use spread-activation and recommendation on this kinds of graphs.},
doi = {10.1145/1557914.1557954},
interhash = {2686bad7ff1f4d07c0b3302dff08368a},
intrahash = {fa98bda69e12481ea7b79d883f54955d},
isbn = {978-1-60558-486-7},
keywords = {best-paper ht09 network-analysis spam tagging},
location = {Torino, Italy},
pages = {229--238},
posted-at = {2009-07-01 12:40:36},
priority = {0},
publisher = {ACM},
series = {HT '09},
timestamp = {2018-03-19T12:24:51.000+0100},
title = {{Hyperincident connected components of tagging networks}},
url = {http://dx.doi.org/10.1145/1557914.1557954},
year = 2009
}