Vol. 5 - Graph and network analysis

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.
Section: Subject Area 3: Graphs and Networks

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.
Section: Subject Area 3: Graphs and Networks

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.
Section: Subject Area 3: Graphs and Networks

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.
Section: Subject Area 3: Graphs and Networks

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

Andrey Grunin.
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.
Section: Subject Area 3: Graphs and Networks

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.
Section: Subject Area 3: Graphs and Networks