Subject Area 3: Graphs and Networks

Communication Network Systems for White Spot Areas

Madoune Seye ; Moussa Diallo ; Bamba Gueye ; Christophe Cambier.
White spot areas depict geographic locations which are not covered by mobile network operators. In Senegal, the Sylvo-pastoral hosted by Ferlo's region has a prominent role according to livestock transhumance. Nevertheless, this region is roughly covered by white spot areas. The lack of cellular network infrastructure is a pitfall for vital information dissemination for agro-pastoralists. Therefore, this paper describes the deployment and testbed performance evaluation in rural and urban environment of a LoRa-based COWShED communication architecture. By leveraging a mesh-based prof-of-concept, tangible results are obtained and thus promote several applications which overcome white spot areas limitations such as stakeholders geolocation, transhumance management, milk collection, etc.

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.

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.

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.

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.

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.

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.

Active learning in annotating micro-blogs dealing with e-reputation

Jean-Valère Cossu ; Alejandro Molina-Villegas ; Mariana Tello-Signoret.
Elections unleash strong political views on Twitter, but what do people really think about politics? Opinion and trend mining on micro blogs dealing with politics has recently attracted researchers in several fields including Information Retrieval and Machine Learning (ML). Since the performance of ML and Natural Language Processing (NLP) approaches are limited by the amount and quality of data available, one promising alternative for some tasks is the automatic propagation of expert annotations. This paper intends to develop a so-called active learning process for automatically annotating French language tweets that deal with the image (i.e., representation, web reputation) of politicians. Our main focus is on the methodology followed to build an original annotated dataset expressing opinion from two French politicians over time. We therefore review state of the art NLP-based ML algorithms to automatically annotate tweets using a manual initiation step as bootstrap. This paper focuses on key issues about active learning while building a large annotated data set from noise. This will be introduced by human annotators, abundance of data and the label distribution across data and entities. In turn, we show that Twitter characteristics such as the author's name or hashtags can be considered as the bearing point to not only improve automatic systems for Opinion Mining (OM) and Topic Classification but also to reduce noise in human annotations. However, a later thorough analysis […]

Contextualizing Geometric Data Analysis and Related Data Analytics: A Virtual Microscope for Big Data Analytics

Fionn Murtagh ; Mohsen Farid.
The relevance and importance of contextualizing data analytics is described. Qualitative characteristics might form the context of quantitative analysis. Topics that are at issue include: contrast, baselining, secondary data sources, supplementary data sources, dynamic and heterogeneous data. In geometric data analysis, especially with the Correspondence Analysis platform, various case studies are both experimented with, and are reviewed. In such aspects as paradigms followed, and technical implementation, implicitly and explicitly, an important point made is the major relevance of such work for both burgeoning analytical needs and for new analytical areas including Big Data analytics, and so on. For the general reader, it is aimed to display and describe, first of all, the analytical outcomes that are subject to analysis here, and then proceed to detail the more quantitative outcomes that fully support the analytics carried out.

Analyse de réseaux criminels de traite des êtres humains: méthodologie, modélisation et visualisation

Bénédicte Lavaud-Legendre ; Cécile Plessard ; Antoine Laumond ; Guy Melançon ; Bruno Pinaud.
Cet article dessine le contexte d'une étude portant sur les réseaux criminels de traite des êtres humains et décrit la rencontre de trois champs disciplinaires engagés dans ces travaux: Droit, Sociologie et Informatique, ainsi que les éléments méthodologiques développés. Il pose les fondations d'une méthodologie venant en appui à l'étude juridique des réseaux criminels, et plus spécifiquement de ceux se livrant à des faits de traite des êtres humains. La ``science des réseaux'' (Network Science), vue à la fois comme une abstraction mathématique et une approche et méthodologie sociologique, sert de socle pour formuler et explorer un faisceau d'hypothèses éclairant le(s) mode(s) opératoire(s) des réseaux criminels. Les leçons apprises, nourries des interactions entre disciplines, permettent de dessiner les axes de travaux futurs pour améliorer la méthodologie avancée.

Introduction to the special issue on Graphs & Social Systems

Vincent Labatut ; Rosa Figueiredo.
The principle of the Journal of Interdisciplinary Methodologies and Issues in Science (JIMIS) is that each issue is a special one, dedicated to a specific topic and handled by guest editors. This issue (the second of the journal) focuses on the use of graphs (and associated analysis tools) to model and study social systems. The guest editors for this issue are Rosa Figueiredo and Vincent Labatut.

The Problem of Action at a Distance in Networks and the Emergence of Preferential Attachment from Triadic Closure

Jérôme Kunegis ; Fariba Karimi ; Sun Jun.
In this paper, we characterise the notion of preferential attachment in networks as action at a distance, and argue that it can only be an emergent phenomenon – the actual mechanism by which networks grow always being the closing of triangles. After a review of the concepts of triangle closing and preferential attachment, we present our argument, as well as a simplified model in which preferential attachment can be derived mathematically from triangle closing. Additionally, we perform experiments on synthetic graphs to demonstrate the emergence of preferential attachment in graph growth models based only on triangle closing.

Brazilian Congress structural balance analysis

Mario Levorato ; Yuri Frota.
In this work, we study the behavior of Brazilian politicians and political parties with the help of clustering algorithms for signed social networks. For this purpose, we extract and analyze a collection of signed networks representing voting sessions of the lower house of Brazilian National Congress. We process all available voting data for the period between 2011 and 2016, by considering voting similarities between members of the Congress to define weighted signed links. The solutions obtained by solving Correlation Clustering (CC) problems are the basis for investigating deputies voting networks as well as questions about loyalty, leadership, coalitions, political crisis and polarization.

Analyse des Préférences et Tournois Pondérés

Alain Guénoche.
Dans de nombreuses etudes expérimentales , on dispose de n ´ eléments ordonnés suivant plusieurs classements (votes, notes ou crit eres). Nous traitons et comparons deuxprobì emes : (i) Etablir un classement unique (ordre total) des n items et (ii) sélectionner les k meilleurs eléments parmi n. Il s'agit, dans les deux cas, de minimiser le nombre de préférences qui vont a l'encontre de ces 5 choix.

Reflections on Studying Signed Networks

Patrick Doreian.
Despite considerable success, the balance theoretic approach to studying signed relations has encountered some serious problems, both substantive and methodological. The more consequential of them are outlined along with reasons for why solving them is critical. In essence, an agenda of research problems is laid out with many juicy problems to solve. These reflections, while setting a context in prior work, are far more concerned about looking to the future and identifying problems whose solutions hold the potential for transforming the field.