[Booby-Funkybeat-hugo]'s cahier de brouillons

Strategies for online inference of model-based clustering in large and growing networks

2010-08-30T06:55:00.000-07:00

In this paper we adapt online estimation strategies to perform model-based clustering on large networks. Our work focuses on two algorithms, the first based on the SAEM algorithm, and the second on variational methods. These two strategies are compared with existing approaches on simulated and real data. We use the method to decipher the connexion structure of the political websphere during the U.S. political campaign in 2008. We show that our online EM-based algorithms offer a good trade-off between precision and speed, when estimating parameters for mixture distributions in the context of random graphs.

Paper is published in AOAS and the pdf is available here.

Clustering based on random graph model embedding vertex features

2010-03-16T04:32:00.000-07:00

Large datasets with interactions between objects are common to numerous scientific fields including the social sciences and biology, as well as being a feature of specific phenomena such as the internet. The interactions naturally define a graph, and a common way of exploring and summarizing such datasets is graph clustering. Most techniques for clustering graph vertices use only the topology of connections, while ignoring information about the vertices’ features. In this paper we provide a clustering algorithm that harnesses both types of data, based on a statistical model with a latent structure characterizing each vertex both by a vector of features and by its connectivity. We perform simulations to compare our algorithm with existing approaches, and also evaluate our method using real datasets based on hypertext documents. We find that our algorithm successfully exploits whatever information is found both in the connectivity pattern and in the features.

The future of Constellations ? Read the paper here or be crafty ;-)

Oh my God, it's full of stars !!

2009-06-06T13:49:00.000-07:00

To get a closer idea of the MixNet algorithm behavior applied on hypertext documents, just take a look at the Exalead application "Constellations".

Enjoy !

MixNet software package

2008-09-15T02:39:00.000-07:00

Estimates the parameters and hidden class variable of a Mixture of Erdös renyi Random Graphs. The estimation is performed for a Bernouilli Mixture. Packages also implement the previous post !

Code : native or R wrapper.

Fast online graph clustering via Erdős–Rényi mixture

2008-08-22T05:40:00.000-07:00

In the context of graph clustering, we consider the problem of simultaneously estimating both the partition of the graph nodes and the parameters of an underlying mixture of affiliation networks. In numerous applications the rapid increase of data size over time makes classical clustering algorithms too slow because of the high computational cost. In such situations online clustering algorithms are an efficient alternative to classical batch algorithms. We present an original online algorithm for graph clustering based on a Erdős–Rényi graph mixture. The relevance of the algorithm is illustrated, using both simulated and real data sets. The real data set is a network extracted from the French political blogosphere and presents an interesting community organization.

Read the Pattern Recognition paper.

Mathematics for Biological Networks

2007-12-03T08:31:00.000-08:00

The "Mathematics for Biological Networks" Conference will be held on December 17-18 2007 at the Institut Henri Poincaré, Paris. It is a free access interdisciplinary conference in the field of network analysis focusing on applications in molecular biology. Students are encouraged to come and take part in discussions. No registration is required.

Automated Metadata Hierarchy Derivation

2006-05-23T00:35:00.000-07:00

L'article présente une méthode automatique pour construire une hierarchie de metadata d'un ensemble de sites web sans passer par utilisation de hierarchies externes déjà prédéfinies.

L'approche, dans nos expérimentation, confirme globalement les informations issues des analyses principalement topologiques (analyse de la connectivité entre les sites) du groupe rtgi : les sites appartenant aux mêmes clusters topologiques partagent en général la même hierarchie de concepts sémantiques.

De l'optimisation et des réglages sont en encore à étudier pour utiliser cette méthode sur des corpus plus importants. Il faudra donc attendre un peu avant de voir une version "flashy" sur l'observatoire présidentielle...

Bravo à Amjad pour son travail et sa présentation à Damas.

MapReduce : parallelisation et distribution

2006-01-17T01:32:00.000-08:00

Que faire quand l'on doit traiter un grand nombre de données et que l'on dispose uniquement de milliers de CPUs ?
Google propose une architecture qui leur permet d'implémenter la parallelisation et la distribution de certaines de leurs tâches (machine learning, distributed sort, etc...). Le principe est de spécifier une fonction map qui calcule des paires de key/value pour générer un ensemble de valeures intermédiaires (paires de key/value) et une fonction reduce qui fusionne toutes les valeures intermédiaires associées aux mêmes clés intermédiaires.

Saturday Night Clever

2005-11-28T06:45:00.000-08:00

Le old school projet CLEVER (Clientside Eigenvector Enhanced Retrieval) développé au laboratoire Almaden d’IBM a été la première tentative d’utilisation de HITS pour créer un moteur de recherche opérationnel. Deux papiers qui fixaient les bases : Mining the Web's Link Structure et Automatic Resource list Compilation by Analyzing Hyperlink Structure and Associated Text.

Judy, arrêtes!

2005-11-01T03:54:00.000-08:00

Un judy array est une struture de données de type tableau associatif (ex: hash table) très rapide pour le stockage et la recherche de valeurs en utilisant des clés integer ou string. Bien que ce soit une structure de données de type array, les Judy array peuvent avoir beaucoup d'indices non assignés. Cette structure est scalable, performante et compacte en mémoire.

Son API permet les manipulations simples (insert, retrieve, delete) et plus complexes (sort, search, count, sequencial access). D'une manière générale Judy (nom de la soeur de l'inventeur Doug Baskins) peut être déployée, quand le nombre de données à stocker en mémoire est important, à la place des structures plus courantes : arrays, sparse arrays, hash tables, B-trees, binary trees, linear lists, etc. pour les algorithmes de tri et de recherche, et les fonctions de comptage.
Le site du projet Judy : http://judy.sourceforge.net/
L'extension perl pour utilliserJudy : Tie::Judy

Document Clustering, Visualization, and Retrieval via Link Mining

2005-10-14T02:38:00.000-07:00

Un article d'un Raghavan (Vijay). (le site de Prabhakar. chercheur à Yahoo! Research)
inter-documents similarity in web search

Pour implémenter ces méthodes, il existe Cluster 3.0 , écrit en C. La librairie est accessible depuis Perl et Python. L'interface Perl pour accéder à la librairie C est disponible sur cpan ou ActiveState.

Montes dans ta chambre et révises ton C

2005-10-06T08:33:00.000-07:00

http://www.library.cornell.edu/nr/bookcpdf.htm

c'est ce que me dit le valeureux thomas drugeon qui n'a rien à envier au capitaine brewster kahle. Voici une de ses carapaces vertes pour : A technical approach for the French Web Legal Deposit.

A survey of eigenvector methods for web et autres curiosités

2005-09-29T16:26:00.000-07:00

Un aperçu intéressant sur les trois algorithmes de classements topologiques [PageRank, Hits, Salsa] des pages/sites sur le web : http://meyer.math.ncsu.edu/Meyer/PS_Files/Survey.pdf. Les points positifs et négatifs sont également étudiés.

Dans le même genre, une présentation pour updater et trouver le vecteur stationnaire d'une chaîne irréductible de markov (PageRank et Salsa) .

Sinon, quelques liens qui donnent des idées...
http://www.comp.hkbu.edu.hk/
http://www.cs.utexas.edu/users/inderjit/courses/dm2000.html
http://genomenews.free.fr/bioinfo.html

Bloom filter

2005-09-23T00:46:00.000-07:00

Le Bloom filter, a été pensé par Burton H.Bloom en 1970. C'est une structure de données, probabiliste, compacte en mémoire, qui est utilisée pour renseigner si un élément est présent ou non dans un ensemble. Les false positives sont possibles mais pas les false negatives. Les élements peuvent uniquement être ajoutés au set, ils ne peuvent pas être enlevés. Plus il y a d'élements dans le set, plus la probablilité d'avoir des false positives est grande.

Le Bloom filter peut être utilisé ainsi dans de nombreuses situations : détection de la langue en vérifiant l'appartenance à un dictionnaire, marquage d'urls pour les crawlers afin de ne pas visiter deux fois les mêmes pages, etc.

Des compléments sur le bloom filter sur Wikipedia.
Utiliser des bloom en perl.
Ajuster ces paramètres.

trier et manipuler les listes et scalaires en perl

2005-09-19T08:41:00.000-07:00

Le module Sort::Maker permet d'une manière simple et efficace de concevoir des fonctions de tris. L'article de l'auteur Uri Guttman.
Pour les traitements rapides de listes List::Util et List::MoreUtils.
Le petit frère de List::Utils, pour les scalars Scalar::Util.
Le module Sort::Radix permet de trier en O(n * k) avec k la taille fixe des éléments à trier.
Le module Sort::External permet de trier des listes ne pouvant pas tenir en mémoire vive en stockant les listes sur différents fichiers temporaires puis en les fusionnant.
Finalement le module qui tue : Sort-Key-0.13

Mining the Web: Discovering Knowledge from Hypertext Data

2005-09-19T04:01:00.000-07:00

La page de Soumen Chakrabarti, auteur du livre Mining the Web, apporte des compléments sur ses recherches en mettant à disposition ses publications et quelques logiciels. Les transparents de ses cours sont également disponibles.

I'm back on the web

2005-09-17T04:53:00.000-07:00

physically and mentally...