The slashdot zoo: mining a social network with negative edges

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.

REFERENCES

• 1: A. T. Balaban and D. J. Klein. Co-authorship, rational ErdQs numbers, and resistance distances in graphs. Scientometrics, 55(1):59--70, 2002.
• 2: P. Chebotarev and E. V. Shamis. On proximity measures for graph vertices. Automation and Remote Control 10, 59:1443--1459, 1998.
• 3: 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.
• 4: Francois Fouss , Alain Pirotte , Jean-Michel Renders , Marco Saerens, Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.355-369, March 2007 [doi>10.1109/TKDE.2007.46]
• 5: R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
• 6: Vicenç Gómez , Andreas Kaltenbrunner , Vicente López, Statistical analysis of the social network and discussion threads in slashdot, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367585]
• 7: P. Hage and F. Harary. Structural Models in Anthropology. Cambridge University Press, 1983.
• 8: Jonathan L. Herlocker , Joseph A. Konstan , Al Borchers , John Riedl, An algorithmic framework for performing collaborative filtering, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.230-237, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312682]
• 9: 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.
• 10: Y. Hou. Bounds for the least Laplacian eigenvalue of a signed graph. Acta Mathematica Sinica, 21(4):955--960, 2005.
• 11: Takahiko Ito , Masashi Shimbo , Taku Kudo , Yuji Matsumoto, Application of kernels to link analysis, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081941]
• 12: Gabriela Kalna , Desmond J. Higham, A clustering coefficient for weighted networks, with application to gene expression data, AI Communications, v.20 n.4, p.263-271, December 2007
• 13: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 14: J. Kandola, J. Shawe-taylor, and N. Cristianini. Learning semantic similarity. In Advances in Neural Information Processing Systems, pages 657--664, 2002.
• 15: D. J. Klein and M. Randiff. Resistance distance. Mathematical Chemistry, 12(1):81--95, 1993.
• 16: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 17: 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.
• 18: Cliff Lampe , Erik Johnston, Follow the (slash) dot: effects of feedback on new members in an online community, Proceedings of the 2005 international ACM SIGGROUP conference on Supporting group work, November 06-09, 2005, Sanibel Island, Florida, USA [doi>10.1145/1099203.1099206]
• 19: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 20: Marc A. Najork , Hugo Zaragoza , Michael J. Taylor, Hits on the web: how does it compare?, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277823]
• 21: M. E. J. Newman. A measure of betweenness centrality based on random walks. Social Networks, 27(1):39--54, 2005.
• 22: 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.
• 23: J. Scott. Social Network Analysis: a Handbook. Sage Publications, 2000.
• 24: Hanghang Tong , Christos Faloutsos , Yehuda Koren, Fast direction-aware proximity for graph mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281272]
• 25: D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, June 1998.
• 26: Scott White , Padhraic Smyth, Algorithms for estimating relative importance in networks, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956782]
• 27: Bo Yang , William Cheung , Jiming Liu, Community Mining from Signed Social Networks, IEEE Transactions on Knowledge and Data Engineering, v.19 n.10, p.1333-1348, October 2007 [doi>10.1109/TKDE.2007.1061]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Experimentation, Theory

Keywords:
link prediction, negative edge, slashdot zoo, social network