Jérôme Kunegis
Andreas Lommatzsch
Christian Bauckhage
ABSTRACT
We analyse the corpus of user relationships of the Slashdot technology news site. The data was collected from the Slashdot Zoo feature where users of the website can tag other users as friends and foes, providing positive and negative endorsements. We adapt social network analysis techniques to the problem of negative edge weights. In particular, we consider signed variants of global network characteristics such as the clustering coefficient, node-level characteristics such as centrality and popularity measures, and link-level characteristics such as distances and similarity measures. We evaluate these measures on the task of identifying unpopular users, as well as on the task of predicting the sign of links and show that the network exhibits multiplicative transitivity which allows algebraic methods based on matrix multiplication to be used. We compare our methods to traditional methods which are only suitable for positively weighted edges.
- A. T. Balaban and D. J. Klein. Co-authorship, rational ErdQs numbers, and resistance distances in graphs. Scientometrics, 55(1):59--70, 2002.Google Scholar
Cross Ref
- P. Chebotarev and E. V. Shamis. On proximity measures for graph vertices. Automation and Remote Control 10, 59:1443--1459, 1998.Google Scholar
- C. de Kerchove and P. V. Dooren. The PageTrust algorithm: how to rank web pages when negative links are allowed? In Proc. SIAM Int. Conf. on Data Mining, pages 346--352, 2008.Google ScholarCross Ref
- F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans. on Knowledge and Data Engineering, 19(3):355--369, 2007. Google ScholarDigital Library
- R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In Proc. Int. Conf. on World Wide Web, pages 403--412, 2004. Google ScholarDigital Library
- V. Gómez, A. Kaltenbrunner, and V. López. Statistical analysis of the social network and discussion threads in Slashdot. In Proc. Int. Conf. on World Wide Web, pages 645--654, 2008. Google ScholarDigital Library
- P. Hage and F. Harary. Structural Models in Anthropology. Cambridge University Press, 1983.Google Scholar
- J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl. An algorithmic framework for performing collaborative filtering. In Proc. Int. Conf. on Research and Development in Information Retrieval, pages 230--237, 1999. Google ScholarDigital Library
- T. Hogg, D. Wilkinson, G. Szabo, and M. Brzozowski. Multiple relationship types in online communities and social networks. In Proc. AAAI Spring Symposium on Social Information Processing, 2008.Google Scholar
- Y. Hou. Bounds for the least Laplacian eigenvalue of a signed graph. Acta Mathematica Sinica, 21(4):955--960, 2005.Google ScholarCross Ref
- T. Ito, M. Shimbo, T. Kudo, and Y. Matsumoto. Application of kernels to link analysis. In Proc. Int. Conf. on Knowledge Discovery in Data Mining, pages 586--592, 2005. Google ScholarDigital Library
- G. Kalna and D. J. Higham. A clustering coefficient for weighted networks, with application to gene expression data. AI Commun., 20(4):263--271, 2007. Google ScholarDigital Library
- S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The EigenTrust algorithm for reputation management in P2P networks. In Proc. Int. Conf. on World Wide Web, pages 640--651, 2003. Google ScholarDigital Library
- J. Kandola, J. Shawe-taylor, and N. Cristianini. Learning semantic similarity. In Advances in Neural Information Processing Systems, pages 657--664, 2002.Google Scholar
- D. J. Klein and M. Randiff. Resistance distance. Mathematical Chemistry, 12(1):81--95, 1993.Google ScholarCross Ref
- R. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete structures. In Proc. Int. Conf. on Machine Learning, pages 315--322, 2002. Google ScholarDigital Library
- J. Kunegis, S. Schmidt, C. Bauckhage, M. Mehlitz, and S. Albayrak. Modeling collaborative similarity with the signed resistance distance kernel. In Proc. Eur. Conf. on Artificial Intelligence, pages 261--265, 2008. Google ScholarDigital Library
- C. Lampe and E. Johnston. Follow the (Slash) dot: Effects of feedback on new members in an online community. In Proc. Int. Conf. on Supporting Group Work, pages 11--20, 2005. Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proc. Int. Conf. on Information and Knowledge Management, pages 556--559, 2003. Google ScholarDigital Library
- M. A. Najork, H. Zaragoza, and M. J. Taylor. Hits on the web: how does it compare? In Proc. Int. Conf. on Research and Development in Information Retrieval, pages 471--478, 2007. Google ScholarDigital Library
- M. E. J. Newman. A measure of betweenness centrality based on random walks. Social Networks, 27(1):39--54, 2005.Google ScholarCross Ref
- L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.Google Scholar
- J. Scott. Social Network Analysis: a Handbook. Sage Publications, 2000.Google Scholar
- H. Tong, C. Faloutsos, and Y. Koren. Fast direction-aware proximity for graph mining. In Proc. Int. Conf. on Knowledge Discovery and Data Mining, pages 747--756, 2007. Google ScholarDigital Library
- D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, June 1998.Google ScholarCross Ref
- S. White and P. Smyth. Algorithms for estimating relative importance in networks. In Proc. Int. Conf. on Knowledge Discovery and Data Mining, pages 266--275, 2003. Google ScholarDigital Library
- B. Yang, W. Cheung, and J. Liu. Community mining from signed social networks. IEEE Trans. on Knowl. and Data Eng., 19(10):1333--1348, 2007. Google ScholarDigital Library
Index Terms
- The slashdot zoo: mining a social network with negative edges
Recommendations
Learning to predict reciprocity and triadic closure in social networks
We study how links are formed in social networks. In particular, we focus on investigating how a reciprocal (two-way) link, the basic relationship in social networks, is developed from a parasocial (one-way) relationship and how the relationships ...
Friendship prediction and homophily in social media
Social media have attracted considerable attention because their open-ended nature allows users to create lightweight semantic scaffolding to organize and share content. To date, the interplay of the social and topical components of social media has ...
Folks in Folksonomies: social link prediction from shared metadata
WSDM '10: Proceedings of the third ACM international conference on Web search and data miningWeb 2.0 applications have attracted a considerable amount of attention because their open-ended nature allows users to create lightweight semantic scaffolding to organize and share content. To date, the interplay of the social and semantic components of ...
Comments