The Web Science Trust

Six Degrees of Separation in Online Society

Zhang, Lei and Tu, Wanqing (2009) Six Degrees of Separation in Online Society. In: Proceedings of the WebSci'09: Society On-Line, 18-20 March 2009, Athens, Greece.

[img] PDF (preprint) - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
PDF (Final Version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Six degrees of separation is a well-known idea that any two people on this planet can be connected via an average number of six steps. Having succeeded in the real world, the theory even directly or indirectly motivated the invention of online societies. However, no much effort has been paid on checking if the theory really holds for online societies whose connection pattern may not be identical to the real world. This paper tries to give an answer to the question by both mathematical modeling and online measurements. The mathematical approach formulates the problem as a Minimum Diameter Problem in graph theory and evaluates the maximum and average values of the number of connections between any two random-selected community members. Measurements are conducted in three different kinds of online societies, namely ArnetMiner for academic researchers, Facebook for students, and Tencent QQ for teenagers in China. Analysis of these measurements verifies our theoretical findings.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:six degrees of separation, social network, minimum diameter problem, small world
Subjects:Web Science Events > Web Science 2009
ID Code:147
Deposited By: W S T Administrator
Deposited On:24 Jan 2009 08:45
Last Modified:25 Oct 2011 16:32

Repository Staff Only: item control page

EPrints Logo
Web Science Repository is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.