bordeaux20132014:info_cours

Instructors: Guy Melançon (email: `Guy dot Melancon at labri dot fr`

), Bruno Pinaud (email: `Bruno dot Pinaud at labri dot fr`

)

**Homeworks**

Homework are short exercises challenging you with notions, concepts or algorithms. You are each time asked to deliver something and upload it on the wiki. Private pages have been built for each one of you.

**Semester assignment / Term (team) project**

Have a look at the term project defense schedule.

L'objectif du projet est d'implémenter la mesure de centralité basé sur des motifs telle qu'elle est décrite dans Ranking of network elements based on functional substructures.

La mesure de centralité sera implémentée à l'aide d'un script Python sous Tulip. Les graphes exemples fournis dans l'article seront utilisés (Figures 1, 2 et 4) pour la validation.

Selon le temps restant, les expérimentations décrites dans l'article sur le réseaux de régulation de E. coli K12 seront reproduites. Dans cette exemple, la mesure de centralité basée sur des motifs permet de retrouver les gènes qui joue un rôle important dans le réseau de régulation des gènes. Le réseau utilisé sera celui là. La colonne 2 contient les gènes régulateurs et la colonne 4 contient les gènes régulés. La section 3 de l'article décrit la méthode utilisée pour créer un réseau de taille raisonnable.

Deliverables: soon to come.

Nous allons utiliser le jeu de données disponible ici qui est la base des courriers électroniques associée au dossier de la faillite de la société Enron en 2001. L'objectif est notamment d'essayer de reconstruire la hiérarchie de l'entreprise et retrouver les personnalités importantes de la société (CEO, vice-présidents, …).

Deliverables: soon to come.

Nous allons utiliser le jeu de données High-energy physics theory citation network qui contiennent des informations sur 27,770 articles traitant de la physique des particules ainsi que les liens de citations entre ces articles de janvier 1993 à avril 2003. A partir de ce genre de réseaux, il faut essayer de répondre aux questions traditionnelles. Il faut montrer les différentes communautés d'auteurs et leur éventuel apparition ou disparition, détecter les articles de références, est-ce que l'on voit des nouveaux auteurs apparaitre/disparaitre, est-ce qu'il y a des auteurs très prolifiques ? Est-ce qu'il y a des thèmes de prédilections, certains thématiques qui apparaissent, qui disparaissent, …

Deliverables: soon to come.

This project consists in building with Tulip and understanding the Marvel universe social graph. See http://exposedata.com/marvel/ to get the data. The goal is to try to analyze the data to find communities and try to figure if this network looks like a social network with real people (see http://arxiv.org/abs/cond-mat/0202174). At least, you have to compute all the metrics given in the paper.

**Deliverables**: All the python scripts you have written (data import, community detection, various metric computation) and a report which with the results and a discussion. It is necessary to compare your results with those of others (the Marvel universe has been studied by many authors).

This project consists in reading, understanding and implementing the Quilts method which can be used to visualize very large layered graphs. We will work with random graphs generated from a given generator (encoded as a Tulip plugin).

**Deliverables**: A C++ or Python Tulip plugin implementing the algorithm *and* some use cases to show the pros and cons of the method. You are expected to reproduce the results found in the paper (on the same data if available). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

This project consists in reading, understanding and implementing the ShriMP visualization technique which is a layout adjustment algorithm. It, for instance, uniformly resizes nodes when requests for more screen space are made. It tries to preserve additional selected properties of the original graph.

**Deliverables**: A Tulip interactor (C++) implementing the algorithm *and* some use cases to show the pros and cons of the method. You are expected to reproduce the results found in the paper (on the same data if available). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

This project consists in reading, understanding and implementing the Frishman & Tal algorithm (2008) computing a drawing for a dynamic network (encoded as a sequence of networks). Their algorithm uses a force-directed variation computing positions of nodes *ahead of time* so nodes move as little as possible.

**Deliverables**: code implementing the layout algorithm as a Tulip (python) plug-in *and* script. You are expected to reproduce the results found in the paper (on the same data if available). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

Potential dataset: EdgeRyders discussion threads (users, comments and nodes)

This project consists in reading, understanding and implementing the Brandes & Wagner algorithm (1997) computing a drawing for a dynamic network (encoded as a sequence of networks). Their algorithm also reaches stability of nodes to preserve the user's mental map although relying on a probabilistic (Bayesian) paradigm.

**Deliverables**: code implementing the layout algorithm as a Tulip (python) plug-in *and* script. You are expected to reproduce the results found in the paper (on the same data if available). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

This project consists in reading, understanding and implementing the technique developed by Bobo Nick and Ulrik Brandes producing a backbone structure for a network. The backbone structure is built from triangles found in the network, seen as basic blocks of all interactions occurring in the network.

It's probably worth to have a look at Bobo Nick's webpage.

**Deliverables**: code implementing the Simmelian backbone computation as a Tulip (python) plug-in *and* script. You are expected to reproduce the results found in the paper (compute backbones on the same data if available). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

This project consists in reading, understanding and implementing the technique developed by Zachary P. Neal producing a projection of a bipartite graph based on a probabilistic interpretation of node co-occurence. The one-mode projection only links nodes when they share a *significant* number of neighbors.

It's probably worth to have a look at Zachary P. Neal's webpage.

**Deliverables**: code implementing the one-mode projection computation as a Tulip (python) plug-in *and* script. You are expected to reproduce the results found in the paper (compute projections on the same data if available). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

This project consists in reading, understanding and implementing the Louvain algorithm computing a community structure for a network. producing a partition of nodes into (more) tightly connected components. You can search the web to find more information on the algorithm and it use. Implementation (including python) of the algorithm certainly are available.

The algorithm is not determinstic, so distinct execution of the algorithm may return different communities. The algorithm can be modified in different ways to try to compute a *consensus* community, or on the contrary end up computing overlapping communities.

**Deliverables**: code implementing the Louvain algorithm, *and the variations you will propose*, as a Tulip (python) plug-in *and* script. You are expected to reproduce the results found in papers (compute communities on the same data if available). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

This project consists in reading and understanding the work of Auber and Chiricota 2007, and implementing a force-directed algorithm taking advantage of the GPU power to speed up the calculation of forces.

**Deliverables**: GPU implementation of a force-directed algorithm, together with benchmark report of its efficiency (as to reproduce the authors' results). Show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

This project consists in understanding the role of the Laplacian matrix of a graph (built from its adjacency matrix). You can search the web to find more information about the Laplacian matrix. It is simply built as where is a *diagonal* matrix with entry equal to the degree of node . Matrix simply is the *adjacency matrix* of the graph with entry only when there is an edge connecting nodes and and otherwise.

The project requires to compute *all* eigenvalues of the Laplacian matrix (using any available package such as `numpy`

, for instance) and build its histogram. The structure of two graphs can then be compared by looking at their eigenvalues histogram. This idea is due to Uwe Nagel from Konstanz.

The project consists in identifying typical structures and characterizing their eigenvalues histograms (cycle, star, tree, clique, etc.). By varying the structure one might understand how the histogram is modified.

The Laplacian *always* admits the constant vector as eigenvector associated with eigenvalue . The eigenvector associated with the next, minimum but non zero, eigenvalue is of particular importance.

Another goal of this project is to look at the coordinates of this eigenvector as a metric computed on nodes of the graph . and look at how the values distribute (look at positive, null or negative values and at how they offer a decomposition of the graph).

The slides on Olivier Schwander's website might prove useful.

**Deliverables**: code implementing the computation of the Laplacian matrix and histogram (can be usefully implemented as a node metric and visualized as a histogram with Tulip). You may also implement decomposition algorithms showing the interest in using the minimum eigenvector as a grpah decomposition (subgraphs, quotient graph, etc.).

This project consists in reading, understanding and implementing Lespinats and Aupetit's paper providing visual feedback on an MDS projection of high-dimensional data. Their idea is actually quite simple. Suppose an MDS projection is given, and select a point in the projection. One can then compute whether the distances of the other points to are faithful using a diverging colormap (as suggested by the ColorBrewer, for instance) so users can evaluate how much distortion there is in the MDS projection.

The project assumes you will use this technique to compare various projection algorithm. A projection can be computed using classical MDS, or using a nearest graph laid out with a force-directed algorithm, for instance.

**Deliverables**: code implementing the computation of the distortion index, as well as the different projections (MDS, force-directed, etc.). You are expected to reproduce the results found in papers, show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

FP7 stands for the 7th Framework Programme, a research and development programme funded by the European Commission. The project consists in analyzing data describing the overall partnerships the FP7 gave rise to. Each line of the accompanying csv sheet indicates an institute or comany took part in a project (multiple lines may concern a same partner, as many as the number of projects it was part of; multiple lines concern a same project, one for each partner).

The data may be investigated to answer tons of questions, *such as*:

- what actors have interacted more than others (are there communities of actors gathering labs and/or companies, for instance)?
- are these communities based on strategic objectives, or other criterion?
- is there a thematic continuum between communities (with some actors embodying this continuity, acting as gatekeepers or
*pivots*)? - does the continuum favor some strategic objectives or any particular scientific area?

- how do competencies distribute over the European territory (the data contains geographical information of actors)

are there European subspaces of research (some themes begin more present in particular places)?

- etc.

etc.

This project consists in building with Tulip and understanding the Marvel Hero Social Network. In this network, there is a link between two characters if they appear together in a comic. See http://exposedata.com/marvel/ and http://exposedata.com/marvel/data/hero-network.csv to get the data. The data may be investigated to answer tons of questions, *such as*:

- find groups of characters which are often appearing together,
- the characters often used,
- etc.

etc.

This project consists in reading, understanding and implementing Flake, Tarjan and Tsioutsiouliklis' paper.

**Deliverables**: code implementing the algorithm. You are expected to reproduce the results found in papers, show the benefits and limitations of the work, discuss the technique in a report and oral presentation.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/bordeaux20132014/info_cours.txt · Last modified: 2013/12/17 09:39 by melancon