After decades of massive digitization, a sub-stantial amount of documents exists in digital form. The accessibility of these documents is strongly impacted by the quality of document indexing. Most of these documents are indexed in noisy versions that include numerous errors. The noise can be due to manual input mistakes or optical character recognition process and results in errors like spelling mistakes, missing characters, and others. This paper presents a study of the impact of noise on document ranking, an essential task in natural language processing (NLP) with wide-ranging practical applications. We provide a deep and quantitative analysis of the impact of recognition errors on document ranking by testing two popular ranking models on several noisy versions of a subset of the MS MARCO passage ranking dataset, with various levels and types of noise. Our study provides insights into the challenges of document ranking under noisy conditions and advocates for developing ranking models that are more robust to noise.

Network embedding, that aims to learn low-dimensional vector representation of nodes such that the network structure is preserved, has gained significant research attention in recent years. However, most state-of-the-art network embedding methods are computationally expensive and hence unsuitable for representing nodes in billion-scale networks. In this paper, we present LouvainNE, a hierarchical clustering approach to network embedding. Precisely, we employ Louvain, an extremely fast and accurate community detection method, to build a hierarchy of successively smaller subgraphs. We obtain representations of individual nodes in the original graph at different levels of the hierarchy, then we aggregate these representations to learn the final embedding vectors. Our theoretical analysis shows that our proposed algorithm has quasi-linear run-time and memory complexity. Our extensive experimental evaluation, carried out on multiple real-world networks of different scales, demonstrates both (i) the scalability of our proposed approach that can handle graphs containing tens of billions of edges, as well as (ii) its effectiveness in performing downstream network mining tasks such as network reconstruction and node classification.

While microblogging-based Online Social Networks have become an attractive data source in emergency situations, overcoming information overload is still not trivial. We propose a framework which integrates natural language processing and clustering techniques in order to produce a ranking of relevant tweets based on their informativeness. Experiments on four Twitter collections in two languages (English and French) proved the significance of our approach.

This paper presents an image segmentation strategy using an idea coming from the social networks analysis domain. This strategy relies on the use of community detection algorithms in order to cluster pixels that belong to the same group of information. The main issue with this approach is that community detection based image segmentation often leads to over-segmented results. In order to address this problem, we propose an algorithm that agglomerates homogeneous regions using their color properties. Our algorithm is tested on the publicly available Berkeley Segmentation Dataset and experimental results show that the proposed algorithm produces sizable segmentation and achieves object-level segmentation to some extent.

Community detection in single layer, isolated networks has been extensively studied in the past decade. However, many real-world systems can be naturally conceptualized as multilayer networks which embed multiple types of nodes and relations. In this paper, we propose algorithm for detecting communities in multilayer networks. The crux of the algorithm is based on the multilayer modularity index Q_M, developed in this paper. The proposed algorithm is parameter-free, scalable and adaptable to complex network structures. More importantly, it can simultaneously detect communities consisting of only single type, as well as multiple types of nodes (and edges). We develop a methodology to create synthetic networks with benchmark multilayer communities. We evaluate the performance of the proposed community detection algorithm both in the controlled environment (with synthetic benchmark communities) and on the empirical datasets (Yelp and Meetup datasets); in both cases, the proposed algorithm outperforms the competing state-of-the-art algorithms.

In this paper, we investigate the role of mentions on tweet propagation. We propose a novel tweet propagation model SIR_MF based on a multiplex network framework, that allows to analyze the effects of mentioning on final retweet count. The basic bricks of this model are supported by a comprehensive study of multiple real datasets and simulations of the model show a nice agreement with the empirically observed tweet popularity. Studies and experiments also reveal that follower count, retweet rate & profile similarity are important factors in gaining tweet popularity and allow to better understand the impact of the mention strategies on the retweet count. Interestingly, we analytically identify a critical retweet rate regulating the role of mention on the tweet popularity. Finally, our data driven simulation demonstrates that the proposed mention recommendation heuristic "Easy-Mention" outperforms the benchmark "Whom-To-Mention" algorithm.

Many real-world networks based on human activities exhibit a bipartite structure. Although bipartite graphs seem appropriate to analyse and model their properties, it has been shown that standard metrics fail to reproduce intricate patterns observed in real networks. In particular, the overlapping of the neighbourhood of communities is difficult to capture precisely. In this work, we tackle this issue by analysing the structure of 4 real-world networks coming from online social activities. We first analyse their structure using standard metrics. Surprisingly, the clustering coefficient turns out to be less relevant than the redundancy coefficient to account for overlapping patterns. We then propose new metrics, namely the dispersion and the monopoly coefficients, and show that they help refining the study of bipartite overlaps. Finally, we compare the results obtained on real networks with the ones obtained on random bipartite models. This shows that the patterns captured by the redundancy and the dispersion coefficients are strongly related to the real nature of the observed overlaps.

In large-scale online complex networks (Wikipedia, Facebook, Twitter, etc.) finding nodes related to a specific topic is a strategic research subject. This article focuses on two central notions in this context: communities (groups of highly connected nodes) and proximity measures (indicating whether nodes are topologically close). We propose a parameterized proximity measure which, given a set of nodes belonging to a community, learns the optimal parameters and identifies the other nodes of this community, called multi-ego-centered community as it is centered on a set of nodes. We validate our results on a large dataset of categorized Wikipedia pages and on benchmarks, we also show that our approach performs better than existing ones. Our main contributions are (i) a new ergonomic parametrized proximity measure, (ii) the automatic tuning of the proximity's parameters and (iii) the unsupervised detection of community boundaries.

The analysis of social networks is a challenging research area, in particular because of their dynamic features. In this paper, we study such evolving graphs through the evolution of their community structure. More specifically, we build on existing approaches for the identification of stable communities over time. This paper presents two contributions.We first propose a new way to compute such stable communities, using a different time scale, called intrinsic time. This intrinsic time is related to the dynamics of the graph (e.g., in terms of link appearance or disappearance) and independent from traditional (extrinsic) time units, like the second. We then show how visualization both at intrinsic and extrinsic time scales can help validating and interpreting the obtained communities. Our results are illustrated on a social network made of contacts among the participants of the 2006 edition of the Infocom conference.

Diffusion phenomena occur in many kinds of real-world complex networks, e.g., biological, information or social networks. Because of this diversity, several types of diffusion models have been proposed in the literature: epidemiological models, threshold models, innovation adoption models, among others. Many studies aim at investigating diffusion as an evolving phenomenon but mostly occurring on static networks, and much remains to be done to understand diffusion on evolving networks. In order to study the impact of graph dynamics on diffusion, we propose in this paper an innovative approach based on a notion of intrinsic time, where the time unit corresponds to the appearance of a new link in the graph. This original notion of time allows us to isolate somehow the diffusion phenomenon from the evolution of the network. The objective is to compare the diffusion features observed with this intrinsic time concept from those obtained with traditional (extrinsic) time, based on seconds. The comparison of these time concepts is easily understandable yet completely new in the study of diffusion phenomena. We experiment our approach on synthetic graphs, as well as on a dataset extracted from the Github sofware sharing platform.

Communities are a powerful tool to describe the structure of complex networks. Algorithms aiming at maximizing a quality function called modularity have been shown to effectively compute the community structure. However, some problems remain: in particular, it is possible to find high modularity partitions in graph without any community structure, in particular random graphs. In this paper, we study the notion of consensual communities and show that they do not exist in random graphs. For that, we exhibit a phase transition based on the strength of consensus: below a given threshold, all the nodes belongs to the same consensual community; above this threshold, each node is in its own consensual community.

While a natural fit for modeling and understanding mobile networks, time-varying graphs remain poorly understood. Indeed, many of the usual concepts of static graphs have no obvious counterpart in time-varying ones. In this paper, we introduce the notion of temporal reachability graphs. A (tau,delta)-reachability graph is a time-varying directed graph derived from an existing connectivity graph. An edge exists from one node to another in the reachability graph at time t if there exists a journey (i.e., a spatiotemporal path) in the connectivity graph from the first node to the second, leaving after t, with a positive edge traversal time tau, and arriving within a maximum delay delta. We make three contributions. First, we develop the theoretical framework around temporal reachability graphs. Second, we harness our theoretical findings to propose an algorithm for their efficient computation. Finally, we demonstrate the analytic power of the temporal reachability graph concept by applying it to synthetic and real-life datasets. On top of defining clear upper bounds on communication capabilities, reachability graphs highlight asymmetric communication opportunities and offloading potential.

Internet maps are generally constructed using the traceroute tool from a few sources to many destinations. It appeared recently that this exploration process gives a partial and biased view of the real topology, which leads to the idea of increasing the number of sources to improve the quality of the maps. In this paper, we present a set of experiments we have conduced to evaluate the relevance of this approach. It appears that the statistical properties of the underlying network have a strong influence on the quality of the obtained maps, which can be improved using massively distributed explorations. Conversely, we show that the exploration process induces some properties on the maps. We validate our analysis using real-world data and experiments and we discuss its implications.