Voici l'article auquel j'ai fait référence ce matin :
Planetary-Scale Views on a Large Instant-Messaging Network
Jure Leskovec and
Eric Horvitz Microsoft Research,
In: Proceedings of WWW 2008, Beijing, China, April 2008.
http://research.microsoft.com/en-us/um/people/horvitz/messenger_graph_www.htm
NDLA : Graphe non orienté de 180 M de sommets, 1, 3 Md d'arètes extrait de l'activité sur MSN 78% des sommets sont interconnectés entre eux par un degré de = séparation < 7, MAX d(sep) = 29
Voici 3 références à propos de l'étude des "complex networks" (dont/donc les réseaux sociaux) :
1. est l'article fondateur de l'étude des complex network (On peut parler de "grands graphes de terrain") : les grands réseaux extraits du monde "réel" ne sont ni completement régulier, ni completement random. Ils ont à la fois une transitivité forte (graphes réguliers) et des chemins courts (graphes random).
2. decrit une autre propriété que l'on retrouve dans ces grand graphes : la distribution des degrées d'incidence suit une loi de puissance. Un modèle de la dynamique d'évolution des graphes est proposé pour expliquer cette propriété (en deux mot : une croissance avec un attachement préférentiel au nœuds déjà fortement connectés).
3. est un article de revue des travaux effectués depuis (mais en 2003) sur ce type réseaux. A voir (entre autre) le tableau page 10.
Emmanuel N.
PS: 3) est sur arXiv il n'y a pas, je pense, de problème à le diffuser. Pour 1) c'est un article de Nature ; je ne sait pas dans qu'elle mesure on peut le diffuser... 2) article de Science : même pb potentiel. (les fichiers sont ici)
Ref. sur un algo très performant de détection de communautés sur les très grands graphes : Fast unfolding of communities in large networks. Authors:Vincent D. Blondel,Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre http://arxiv.org/abs/0803.0476
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks.
Voici la référence fournie par Zaiane sur l'article relatif à la fouille de réseaux multi-relationnels.
Flavia Moser, Recep Colak, Arash Rafiey, Martin Ester: Mining Cohesive Patterns from Graphs with Feature Vectors. SDM 2009: 593-604
le lien vers l'article : http://www.siam.org/proceedings/datamining/2009/dm09_055_moserf.pdf
le bibtex
@inproceedings{DBLP:conf/sdm/MoserCRE09,
author = {Flavia Moser and
Recep Colak and
Arash Rafiey and
Martin Ester},
title = {Mining Cohesive Patterns from Graphs with Feature Vectors},
booktitle = {SDM},
year = {2009},
pages = {593-604},
ee = {http://www.siam.org/proceedings/datamining/2009/dm09_055_moserf.pdf},
crossref = {DBLP:conf/sdm/2009},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{DBLP:conf/sdm/2009,
title = {Proceedings of the SIAM International Conference on Data
Mining, SDM 2009, April 30 - May 2, 2009, Sparks, Nevada,
USA},
booktitle = {SDM},
publisher = {SIAM},
year = {2009},
bibsource = {DBLP, http://dblp.uni-trier.de}
}