Analysis of networks and graphs

Les réseaux constituent un modèle d'information et de connaissances indispensable pour modéliser et simuler divers types de systèmes : sociaux, biologiques, informatiques, et autres. De part leur nature très générique, il est possible de sélectionner une méthode conçue pour traiter un système donné, et de l'appliquer dans un contexte complètement différent. Par exemple, une méthode permettant de détecter des protéines importantes d'un point de vue fonctionnel dans un réseau biologique peut être utilisée pour identifier des acteurs influents au sein d'un médial social. Cependant, il est très difficile pour un chercheur de se tenir au courant des méthodes développées dans d'autres champs, pour des raisons de différences lexicales, méthodologiques et culturelles. Le but de ce numéro spécial est de tenter de jeter un pont par dessus les différences disciplinaires, en explosant les chercheurs à des outils et usages du concept de graphe étrangers à leur propre champ. L'idée générale est de décrire des méthodes d'analyse de graphes et/ou leur application à des systèmes spécifiques. Nous sommes intéressés par des travaux proposant de nouvelles méthodes d'analyse ou d'extraction de graphe, susceptibles d'être utilisées dans des contextes applicatifs très différents. Nous visons aussi des travaux décrivant comment une méthode existante, initialement développée pour un contexte donné, a été adaptée et/ou appliquée à des graphes représentant des systèmes différents. Enfin, nous sommes aussi intéressés par des travaux traitant de systèmes aux propriétés uniques, nécessitant la conception de méthodes spécifiques au domaine concerné.

1. Introduction to the special issue on Graph and Network Analysis

Vincent Labatut.
This fifth issue of the Journal of Interdisciplinary Methodologies and Issues in Science (JIMIS) is dedicated to methods designed for the analysis of graphs and networks, as well as to applied works relying on the analysis of graphs and networks in specific domains. It can be considered as a follow-up of the second issue of JIMIS, which focused on the modeling of social systems through graphs. Like before, it includes strongly interdisciplinary works. In addition, this issue widens the scope of the considered problems and systems, as the focus is not only on social systems anymore.

2. Sur la chronologie des éponymes rhodiens

Alain Guénoche.
Par une méthode de sériation appliquéè a une matrice binaire, on essaye de retrouver l'ordre chro-nologique des Prêtres d'Hélios de l'île de Rhodes à la période hellénistique. La table binaire est celle de la correspondance entre ces magistrats changés chaque année et des fabricants de vin qui exportaient leur production dans des amphores marquées de leurs deux sceaux. L'optimisation d'un critère sur l'ensemble des ordres de 205 prêtres permet d'établir une chronologie compatible avec les données archéologiques connues.

3. A general graph-based framework for top-N recommendation using content, temporal and trust information

Armel Jacques Nzekon Nzeko'O ; Maurice Tchuenté ; Matthieu Latapy.
Recommending appropriate items to users is crucial in many e-commerce platforms. One common approach consists in selecting the N most relevant items for each user. To achieve this, recom-mender systems rely on various kinds of information, like item and user features, past interest of users for items and trust between users. Current systems generally use only one or two such pieces of information, which limits their performance. In this paper, we design and implement GraFC2T2, a general graph-based framework to easily combine various kinds of information for top-N recommendation. It encodes content-based features, temporal and trust information into a graph model, and uses personalized PageRank on this graph to perform recommendation. Experiments are conducted on Epinions and Ciao datasets, and comparisons are done with systems based on matrix factorization and deep learning using F1-score, Hit ratio and MAP evaluation metrics. The results show that combining different kinds of information generally improves recommendation. This shows the relevance of the proposed framework.

4. Predicting interactions between individuals with structural and dynamical information

Thibaud Arnoux ; Lionel Tabourier ; Matthieu Latapy.
Capturing both structural and temporal features of interactions is crucial in many real-world situations like studies of contact between individuals. Using the link stream formalism to model data, we address here the activity prediction problem: we predict the number of links that will occur during a given time period between each pair of nodes. To do this, we take benefit from the temporal and structural information captured by link streams. We design and implement a modular supervised learning method to make prediction, and we study the key elements influencing its performances. We then introduce classes of node pairs, which improves prediction quality and increases diversity.

5. Réseau politique des agents du pouvoir central : l'exemple des missi dominici

Andrey Grunin.
Cette étude propose plusieurs modèles d’analyse d’un réseau politique des agents du pouvoir central du haut Moyen Âge, les missi dominici. Complétées par l’analyse statistique, plusieurs hypothèses de recherche fondées sur les positions de l’historiographie actuelle ont été étayées. D’une part, l’examen du réseau des agents a permis de mettre en lumière une certaine évolution liée à la structuration du système missatique et au mécanisme de la transition des agents d’un règne à l’autre. D’autre part, l’étude des relations entre les agents et les lieux de leurs missions a confirmé une certaine amplification, avec le temps, de la politique du recrutement des missi au sein de l’aristocratie locale. Enfin, plusieurs difficultés liées tant au caractère lacunaire des données issues des sources médiévales qu’à la complexité de modélisation et d’analyse d’un réseau politique multimodal ont été évoquées.

6. Multi-dimensional Urban Network Percolation

Juste Raimbault.
Network percolation has recently been proposed as a method to characterize the hierarchical structure of an urban system from the bottom-up. This paper proposes to extend urban network per-colation in a multi-dimensional way, to take into account both urban form (spatial distribution of population) and urban functions (here as properties of transportation networks). The method is applied to the European urban system to reconstruct endogenous urban regions. The variable parametrization allows to consider patterns of optimization for two stylized contradictory sustainability indicators (economic performance and greenhouse gases emissions). This suggests a customizable spatial design of policies to develop sustainable territories.