Characterizing LiveJournal

Characterizing LiveJournal: SCCs, LiveRank, & Six Degrees
Yevgeniy 'Eugene' Medynskiy and Joseph 'Jofish' Kaye, Cornell Information Science
ym66 | jofish at cornell.edu

---

Main Result:

• LiveJoural is in a Strongly-Connected Component (SCC).
• On average, users are 5.81 friends apart: six degree of separation.
• At most, users 10 steps apart
• Fraction with i in-link: Power-law network: 1/(i^2.65)
• 81.5% users in the core LiveJoural SCC
• 17.1% single-member
• other 11,682 SCC ranging in size from 65 to 2 for online role-playing games, etc.

Info:

• 5% people in Massachusetts has a LiveJoural blog.
• 80% of blog friendship are reciprocated [1]. It is a important characteristic different from internet. The result is: 81.5% users in the core LiveJoural SCC, but only 30% pages in the internet SCC [3].
• LJ friends graph from Kirsten Hildrum at IBM Watson shows mean number of friends is 12.95 with median 5 friends. [2]
• In 1999, Broder et. al. described the shape of the WWW as a whole at that time as being bowtieshaped. [3].
• Algorithm to find SCC [4], Optimization [5], Discussion [6]
• Breadth-first search to find diameter. [2]
• They use AT&T Neato tool including the Graphwiz package to visualize the SCC.
• Internet 6 degree paper [7], Small world problem [8]

Question:

• As explained by the author, the In-link can not represent the friend relationship.If we analyze the Out-link, I believe it shall be exponential networks distribution. I am puzzled why the author didn't analyze the out-link data. Is it investigated?

Reference:

1. R. Kumar, J. Novak, P. Raghavan, A. Tomkins. Structure and Evolution of Blogspace. Communications of the ACM. 47:12.35-39.
2. Hildrum, Kirsten. Some statistics. Post in lj_research. http://www.livejournal.com/community/lj_research/13741.html
3. A. Barabasi and R. Albert. Emergence of scaling in random networks, Science, 286(509), 1999.
4. Tarjan, Robert. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput 1(2) 1972.
5. Jiang, Bin. I/O- and CPU-optimal recognition of strongly connected components. Information
   Processing Letters 45 (1993) 111-115
6. Esko Nuutila, Eljas Soisalon-Soininen: On Finding the Strongly Connected Components in a Directed Graph. Inf. Process. Lett. 49(1): 9-14 (1994)
7. R. Albert, H. Jeong, A. Barabasi. Diameter of the World-Wide Web. Nature 401:130-131, 1999.
8. S. Milgram. The small world problem. Psychology Today 1:61-67, 1967.

Technorati : Blog, LiveJournal, Reciprocation