Analysis of networks and graphs

Networks have become invaluable to model and simulate a number of real-world systems: social, biological, computer-related, or otherwise. Thanks to their generic nature, it is possible to take a method designed to handle a specific system, and apply it in a completely different context. For instance, a method allowing to detect functionally important proteins in a biological network can be used to identify key-players in a social network. However, due to lexical, methodological and cultural differences, being aware of methods developed in other fields can be truly challenging for a researcher. The goal of this special issue is to try to bridge this gap between scientific fields, by exposing researchers to different tools and usages of the concept of graph, coming from out of their field. The general idea is to describe graph analysis methods and/or their application to specific social systems. We are interested in works proposing new analysis or extraction methods, likely to be used in various very different application contexts. We are also interested in works describing how an existing method, initially developed for a given context, was adapted and/or applied to graphs representing completely different systems. Finally, we are interested as well in works dealing with systems whose unique properties require the design of domain-specific methods.

1. Sur la chronologie des éponymes rhodiens

Guénoche, Alain.
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.

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

Nzekon Nzeko'O, Armel Jacques ; Tchuenté, Maurice ; Latapy, Matthieu.
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 […]

3. Predicting interactions between individuals with structural and dynamical information

Arnoux, Thibaud ; Tabourier, Lionel ; Latapy, Matthieu.
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.

4. Political network of central power agents: case of missi dominici

Grunin, Andrey.
This study offers several models of social network analysis to examine the organization of central power agents, missi dominici, during the Early Middle Ages. Enriched by statistical analysis, different research hypotheses based on the current historiographical positions have been substantiated. On the one side, the network analysis allowed to highlight the evolution of network structure throughout the studied period and to observe a change in the framework of agents transition between reigns. On the other side, the statistical exploration of the relations between the agents and the places of their assignments confirmed some amplification, with time, of a tendency to recruit the agents among the local aristocracy. Finally, several difficulties related to the analyzing of missing data provided by fragmentary historical records as well as to modeling a complex multimodal political network were mentioned.