Introduction to Social Networks on Web
Report on the presentation of Pierre Senellart, December 11, 2008.
See slides for more details.
Warning : this report outlines the understanding of the post author (Alban Galland) and nothing more.
Typology
Definition : a social content web site is a web site with users, content and implicit or explicit links between users.
This definition, rather large, cover as much the sites of blogs and of multimedia content as explicitly social networks (SN) based sites. The social content web sites are users based or content based. The users based site may be pure SN (professional as LinkedIn, friendship as MySpace or mixed as FaceBook), blog communities (SkyRock) or dating-sites (Meetic). The content based sites are sites where users could share or annotate content and meet through common interests. they could be catalogs of content (from Music as LastFm to bookmarks as delicious), content-sharing sites (pictures as flickr, videos as YouTube), content-producing site (wikipedia, forums, Yahoo! Answer…) or web-shop (ebay or Amazon).
Models
The natural model is a graph, directed or undirected, which could be multipartite (users, content, tags …). The links between users could be explicit (bridging links, declaration) or implicit (bonding links, through content).
The SN graphs are characterized by
- sparse graph
- small distances (small world graph, 6 degrees of separation theory)
- high transitivity (clustering : two nodes close from a third one are likely to be close themselves)
- degree distribution follows a power-law
SN are not randoms graph (which could be only sparse with small distance) nor random modification of a regular grid (which could be only sparse, with small distance and high transitivity). They are closer from free-scale graph, build by adding nodes one by one and linking each new node in order to preserve the property described above.
Algorithms
- PageRank : this algorithm is used to rank mode in a graph according to their importance in the graph. It is not helpful on undirected graph since it converges to the degree of the node, but variants exists.
- Search of communities : extract communities from the graph could be done using minimum cut/maximum flow algorithms or Markov clustering algorithms (MCL, removing betweeness edges)
- Improve Information Retrieval : the tags could be used to improve semantic search. recommendation is also a topic of interest , using Collaborative filtering (user-based) or item based recommendation.Finally IR could be biased with distance on the SN graph
Conclusion
- SN is larger than FaceBook!
- There is some natural models and some natural research on IR, trust …