Qualitative Comparison of Community Detection Algorithms

Community detection is a very active field in complex networks analysis, consisting in identifying groups of nodes more densely interconnected relatively to the rest of the network. The existing algorithms are usually tested and compared on real-world and artificial networks, their performance being assessed through some partition similarity measure. However, artificial networks realism can be questioned, and the appropriateness of those measures is not obvious. In this study, we take advantage of recent advances concerning the characterization of community structures to tackle these questions. We first generate networks thanks to the most realistic model available to date. Their analysis r…

Choosing Optimal Seed Nodes in Competitive Contagion.

International audience; In recent years there has been a growing interest in simulating competitive markets to find out the efficient ways to advertise a product or spread an ideology. Along this line, we consider a binary competitive contagion process where two infections, A and B, interact with each other and diffuse simultaneously in a network. We investigate which is the best centrality measure to find out the seed nodes a company should adopt in the presence of rivals so that it can maximize its influence. These nodes can be used as the initial spreaders or advertisers by firms when two firms compete with each other. Each node is assigned a price tag to become an initial advertiser whi…

Community-based method for extracting backbones

Networks are an adequate representation for modeling and analyzing a great variety of complex systems. However, understanding networks with millions of nodes and billions of connections can be pretty challenging due to memory and time constraints. Therefore, selecting the relevant nodes and edges of these large-scale networks while preserving their core information is a major issue. In most cases, the so-called backbone extraction methods are based either on coarse-graining or filtering approaches. Coarse-graining techniques reduce the network size by gathering similar nodes into super-nodes, while filter-based methods eliminate nodes or edges according to a statistical property. In this wo…

A New Image Distortion Measure Based on Natural Scene Statistics Modeling

In the field of Image Quality Assessment (IQA), this paper examines a Reduced Reference (RRIQA) measure based on the bi-dimensional empirical mode decomposition. The proposed measure belongs to Natural Scene Statistics (NSS) modeling approaches. First, the reference image is decomposed into Intrinsic Mode Functions (IMF); the authors then use the Generalized Gaussian Density (GGD) to model IMF coefficients distribution. At the receiver side, the same number of IMF is computed on the distorted image, and then the quality assessment is done by fitting error between the IMF coefficients histogram of the distorted image and the GGD estimate of IMF coefficients of the reference image, using the …

A comparison of community-aware centrality measures in online social networks

A General Framework for Complex Network-Based Image Segmentation

International audience; With the recent advances in complex networks theory, graph-based techniques for image segmentation has attracted great attention recently. In order to segment the image into meaningful connected components, this paper proposes an image segmentation general framework using complex networks based community detection algorithms. If we consider regions as communities, using community detection algorithms directly can lead to an over-segmented image. To address this problem, we start by splitting the image into small regions using an initial segmentation. The obtained regions are used for building the complex network. To produce meaningful connected components and detect …

Investigating the Relationship Between Community-aware and Classical Centrality Measures

International audience

Movie Script Similarity Using Multilayer Network Portrait Divergence

International audience; This paper addresses the question of movie similarity through multilayer graph similarity measures. Recent work has shown how to construct multilayer networks using movie scripts, and how they capture different aspects of the stories. Based on this modeling, we propose to rely on the multilayer structure and compute different similarities, so we may compare movies, not from their visual content, summary, or actors, but actually from their own storyboard. We propose to do so using “portrait divergence”, which has been recently introduced to compute graph distances from summarizing graph characteristics. We illustrate our approach on the series of six Star Wars movies.

A Modularity Backbone Extraction Method for Weighted Complex Networks

The exponential growth in the size of real-world networks is a major barrier to analyzing their structure and dynamics. Thus, reducing the network's size while maintaining its topological features is highly significant. As community structure is one of the fundamental fingerprints of real-world networks, this work proposes a new node-filtering backbone extraction method to preserve the network's community structure.

An empirical study on classical and community-aware centrality measures in complex networks

Community structure is a ubiquitous feature in natural and artificial systems. Identifying key nodes is a fundamental task to speed up or mitigate any diffusive processes in these systems. Centrality measures aim to do so by selecting a small set of critical nodes. Classical centrality measures are agnostic to community structure, while community-aware centrality measures exploit this property. Several works study the relationship between classical centrality measures, but the relationship between classical and community-aware centrality measures is almost unexplored. In this work [1], we answer two questions: (1) How do classical and community-aware centrality measures relate? (2) What is …

National Migration in rural Germany -A complex network perspective on interdependencies for elderly migration and well-being

Spatial planning decisions have to consider complex networks of influences in order to deliver sustainable results. For example, the construction of a retirement home may cause older people to migrate from the aging single-family home areas (SFHA) in the surrounding region.The answer to the question if and where to migrate is an individual human decision and thus depends not only on the surrounding circumstances and influences but also on the experiencesand knowledge every individual has. Therefore, the analysis has to incorporate data on the influences as well as data on the individual subjects as well. There are several approaches inthe field of well-being and quality of life research. Th…

A Community-Aware Backbone Extractor for Weighted Networks

International audience

Finding Influential Nodes in Networks with Community Structure

International audience; Identifying influential nodes is a fundamental issue in complex networks. Several centrality measures take advantage of various network topological properties to target the top spreaders. However, the vast majority of works ignore its community structure while it is one of the main properties of many real-world networks. In our previous work 4 , we show that the centrality of a node in a network with non-overlapping communities depends on two features: Its local influence on the nodes belonging to its community, and its global influence on nodes belonging to the other communities. For this end, we introduced a framework to adapt all the classical centrality measures …

Integrating Environmental Temperature Conditions into the SIR Model for Vector-Borne Diseases

International audience; Nowadays, Complex networks are used to model and analyze various problems of real-life e.g. information diffusion in social networks, epidemic spreading in human population etc. Various epidemic spreading models are proposed for analyzing and understanding the spreading of infectious diseases in human contact networks. In classical epidemiological models, a susceptible person becomes infected after getting in contact with an infected person among the human population only. However, in vector-borne diseases, a human can be infected also by a living organism called a vector. The vector population that also help in spreading diseases is very sensitive to environmental f…

A blind Robust Image Watermarking Approach exploiting the DFT Magnitude

Due to the current progress in Internet, digital contents (video, audio and images) are widely used. Distribution of multimedia contents is now faster and it allows for easy unauthorized reproduction of information. Digital watermarking came up while trying to solve this problem. Its main idea is to embed a watermark into a host digital content without affecting its quality. Moreover, watermarking can be used in several applications such as authentication, copy control, indexation, Copyright protection, etc. In this paper, we propose a blind robust image watermarking approach as a solution to the problem of copyright protection of digital images. The underlying concept of our method is to a…

Influential Spreaders in Networks with Community Structure

International audience; Hassouni (2019). Centrality in Complex Networks with overlapping Community structure. Scientific Reports, 9(1).

Reduced Reference Mesh Visual Quality Assessment Based on Convolutional Neural Network

3D meshes are usually affected by various visual distortions during their transmission and geometric processing. In this paper we propose a reduced reference method for mesh visual quality assessment. The method compares features extracted from the distorted mesh and the original one using a convolutional neural network in order to estimate the visual quality score. The perceptual distance between two meshes is computed as the Kullback-Leibler divergence between the two sets of feature vectors. Experimental results from two subjective databases (LIRIS masking database and LIRIS/EPFL general purpose database) and comparisons with seven objective metrics cited in the state-of-the-art demonstr…

Image Quality Assessment Based on Intrinsic Mode Function Coefficients Modeling

Reduced reference image quality assessment (RRIQA) methods aim to assess the quality of a perceived image with only a reduced cue from its original version, called ”reference image”. The powerful advantage of RR methods is their ”General-purpose”. However, most introduced RR methods are built upon a non-adaptive transform models. This can limit the scope of RR methods to a small number of distortion types. In this work, we propose a bi-dimensional empirical mode decomposition-based RRIQA method. First, we decompose both, reference and distorted images, into Intrinsic Mode Functions (IMF), then we use the Generalized Gaussian Density (GGD) to model IMF coefficients. Finally, the distortion m…

Measuring Movie Script Similarity using Characters, Keywords, Locations, and Interactions

Measuring similarity between multilayer networks is difficult, as it involves various layers and relationships that are challenging to capture using distance measures. Existing techniques have focused on comparing layers with the same number of nodes and ignoring interrelationships. In this research, we propose a new approach for measuring the similarity between multilayer networks while considering interrelationships and networks of various sizes. We apply this approach to multilayer movie networks composed of layers of different entities (character, keyword, and location) and interrelationships between them. The proposed method captures intra-layer and inter-layer relationships, providing…

An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph

International audience; In this article we characterize bipartite graphs whose associated neighborhood hypergraphs have the Helly property. We examine incidence graphs both hypergraphs and linear hypergraphs and we give a polynomial algorithm to recognize if a linear hypergraph has the Helly property.

A segmentation algorithm for noisy images

International audience; This paper presents a segmentation algorithm for gray-level images and addresses issues related to its performance on noisy images. It formulates an image segmentation problem as a partition of a weighted image neighborhood hypergraph. To overcome the computational difficulty of directly solving this problem, a multilevel hypergraph partitioning has been used. To evaluate the algorithm, we have studied how noise affects the performance of the algorithm. The alpha-stable noise is considered and its effects on the algorithm are studied. Key words : graph, hypergraph, neighborhood hypergraph, multilevel hypergraph partitioning, image segmentation and noise removal.

Backbone Extraction of Weighted Modular Complex Networks based on their Component Structure

This work introduces a generic backbone extraction framework exploiting the mesoscopic network structure. Indeed, numerous real-world networks are made of dense groups of nodes called communities, multi-core or local components. To deal with these groups' heterogeneity, we propose to extract the backbones independently from their various components and fuse them. Experimental investigations on real-world networks demonstrate the effectiveness of the proposed approach compared to the classical techniques' agnostic of the mesoscopic structure of real-world networks.

Towards realistic artificial benchmark for community detection algorithms evaluation

Many algorithms have been proposed for revealing the community structure in complex networks. Tests under a wide range of realistic conditions must be performed in order to select the most appropriate for a particular application. Artificially generated networks are often used for this purpose. The most realistic generative method to date has been proposed by Lancichinetti, Fortunato and Radicchi (LFR). However, it does not produce networks with some typical features of real-world networks. To overcome this drawback, we investigate two alternative modifications of this algorithm. Experimental results show that in both cases, centralisation and degree correlation values of generated networks…

Complex Networks & Their Applications VII

International audience

Characterizing the Relation between Hubs and Overlapping Nodes in Modular Networks

International audience

Overlapping Community Structure in Co-authorship Networks: A Case Study

Community structure is one of the key properties of real-world complex networks. It plays a crucial role in their behaviors and topology. While an important work has been done on the issue of community detection, very little attention has been devoted to the analysis of the community structure. In this paper, we present an extensive investigation of the overlapping community network deduced from a large-scale co-authorship network. The nodes of the overlapping community network represent the functional communities of the co-authorship network, and the links account for the fact that communities share some nodes in the co-authorship network. The comparative evaluation of the topological prop…

Convolutional Neural Network for Blind Mesh Visual Quality Assessment Using 3D Visual Saliency

In this work, we propose a convolutional neural network (CNN) framework to estimate the perceived visual quality of 3D meshes without having access to the reference. The proposed CNN architecture is fed by small patches selected carefully according to their level of saliency. To do so, the visual saliency of the 3D mesh is computed, then we render 2D projections from the 3D mesh and its corresponding 3D saliency map. Afterward, the obtained views are split to obtain 2D small patches that pass through a saliency filter to select the most relevant patches. Experiments are conducted on two MVQ assessment databases, and the results show that the trained CNN achieves good rates in terms of corre…

Comparing Link Filtering Backbone Techniques in Real-World Networks

Assessing movie similarity using a multilayer network model

International audience; This work investigates the movie similarity issue. A multilayer network model capturing various aspects of the story is built from movie scripts. Based on this representation, movies are compared not from summary or actors but using their storyboard. We rely on the "Portrait divergence" to quantify distances between graph characteristics. We illustrate the effectiveness of this approach in comparing movie series.

Influential Spreaders in Modular Networks

International audience; Hassouni (2019). Centrality in Complex Networks with overlapping Community structure. Scientific Reports, 9(1).

User and group networks on YouTube: A comparative analysis

International audience; YouTube is the largest video-sharing social network where users (aka channels) can create links to any other users. Moreover, initially, users were allowed to create and join special groups of interest. Therefore, two types of online social networks can be defined. First, a user network where the nodes represent the users and the edges represent the social ties (friendship) between users. Second, a group network where the nodes represent the groups and the edges represent the social ties between groups, due to shared users. As the group network can be apprehended as the ground-truth overlapping community graph (where the nodes are the discovered communities and the l…

Community detection algorithm evaluation with ground-truth data

International audience; Community structure is of paramount importance for the understanding of complex networks. Consequently, there is a tremendous effort in order to develop efficient community detection algorithms. Unfortunately, the issue of a fair assessment of these algorithms is a thriving open question. If the ground-truth community structure is available, various clustering-based metrics are used in order to compare it versus the one discovered by these algorithms. However, these metrics defined at the node level are fairly insensitive to the variation of the overall community structure. To overcome these limitations, we propose to exploit the topological features of the ‘communit…

Centrality measures for networks with community structure

Understanding the network structure, and finding out the influential nodes is a challenging issue in the large networks. Identifying the most influential nodes in the network can be useful in many applications like immunization of nodes in case of epidemic spreading, during intentional attacks on complex networks. A lot of research is done to devise centrality measures which could efficiently identify the most influential nodes in the network. There are two major approaches to the problem: On one hand, deterministic strategies that exploit knowledge about the overall network topology in order to find the influential nodes, while on the other end, random strategies are completely agnostic ab…

Extracting modular-based backbones in weighted networks

Abstract Networks are an adequate representation for modeling and analyzing a great variety of complex systems. However, understanding networks with millions of nodes and billions of connections can be pretty challenging due to memory and time constraints. Therefore, selecting the relevant nodes and edges of these large-scale networks while preserving their core information is a major issue. In most cases, the so-called backbone extraction methods are based either on coarse-graining or filtering approaches. Coarse-graining techniques reduce the network size by gathering similar nodes into super-nodes, while filter-based methods eliminate nodes or edges according to a statistical property.In…

Searching for Influential Nodes in Modular Networks

International audience

An Efficient Immunization Strategy Using Overlapping Nodes and Its Neighborhoods

International audience; When an epidemic occurs, it is often impossible to vaccinate the entire population due to limited amount of resources. Therefore, it is of prime interest to identify the set of influential spreaders to immunize, in order to minimize both the cost of vaccine resource and the disease spreading. While various strategies based on the network topology have been introduced, few works consider the influence of the community structure in the epidemic spreading process. Nowadays, it is clear that many real-world networks exhibit an overlapping community structure, in which nodes are allowed to belong to more than one community. Previous work shows that the numbers of communit…

Analyzing the Correlation of Classical and Community-aware Centrality Measures in Complex Networks

International audience; Identifying influential nodes in social networks is a fundamental issue. Indeed, it has many applications, such as inhibiting epidemic spreading, accelerating information diffusion, preventing terrorist attacks, and much more. Classically, centrality measures quantify the node's importance based on various topological properties of the network, such as Degree and Betweenness. Nonetheless, these measures are agnostic of the community structure, although it is a ubiquitous characteristic encountered in many real-world networks. To overcome this drawback, there is a growing trend to design so-called community-aware centrality measures. Although several works investigate…

Localization of Hubs in Modular Networks

International audience

A Curvature Based Method for Blind Mesh Visual Quality Assessment Using a General Regression Neural Network

International audience; No-reference quality assessment is a challenging issue due to the non-existence of any information related to the reference and the unknown distortion type. The main goal is to design a computational method to objectively predict the human perceived quality of a distorted mesh and deal with the practical situation when the reference is not available. In this work, we design a no reference method that relies on the general regression neural network (GRNN). Our network is trained using the mean curvature which is an important perceptual feature representing the visual aspect of a 3D mesh. Relatively to the human subjective scores, the trained network successfully asses…

How Correlated Are Community-Aware and Classical Centrality Measures in Complex Networks?

Unlike classical centrality measures, recently developed community-aware centrality measures use a network’s community structure to identify influential nodes in complex networks. This paper investigates their relationship on a set of fifty real-world networks originating from various domains. Results show that classical and community-aware centrality measures generally exhibit low to medium correlation values. These results are consistent across networks. Transitivity and efficiency are the most influential macroscopic network features driving the correlation variation between classical and community-aware centrality measures. Additionally, the mixing parameter, the modularity, and the Max…

Filtering Real World Networks: A Correlation Analysis of Statistical Backbone Techniques

Networks are an invaluable tool for representing and understanding complex systems. They offer a wide range of applications, including identifying crucial nodes, uncovering communities, and exploring network formation. However, when dealing with large networks, the computational challenge can be overwhelming. Fortunately, researchers have developed several techniques to address this issue by reducing network size while preserving its fundamental properties [1-9]. To achieve this goal, two main approaches have emerged: structural and statistical methods. Structural methods aim to keep a set of topological features of the network while reducing its size. In contrast, statistical methods elimi…

K-Way Hypergraph Partitioning And Color Image Segmentation

International audience

Exploring network distances for movies comparison

International audience

Graphes multicouches pour mesurer la similarité entre des films

Un système de recommandation des films propose à ses utilisateurs un ensemble de films similaires à leurs séries préférées, en se basant sur le principe de filtration, par exemple la filtration de leurs données personnelles. Ces dernières années, les réseaux sociaux sont devenus de plus en plus utilisés pour représenter et analyser des histoires de films[1][2][3]. Une étude [6] s'est appuyée sur les réseaux sociaux pour classifier les films par genre. D'autres études [4][5] ont utilisé les réseaux sociaux pour analyser des films à partir des rôles des personnages. A notre connaissance, il n'existe pas une technique qui permet de trouver la similarité entre deux films en calculant la distanc…

Identifying Influential Nodes: The Overlapping Modularity Vitality Framework

This paper proposes an Overlapping Modularity Vitality framework for identifying influential nodes in networks with overlapping community structures. The framework uses a generalized modularity equation and the concept of vitality to calculate the centrality of a node. We investigate three definitions of overlapping modularity and three ranking strategies prioritizing hubs, bridges, or both types of nodes. Experimental investigations involving real-world networks show that the proposed framework demonstrates the benefit of incorporating overlapping community structure information to identify critical nodes in a network.

An Empirical Comparison of Centrality and Hierarchy Measures in Complex Networks

International audience

Image Segmentation by Deep Community Detection Approach

International audience; To address the problem of segmenting an image into homogeneous communities this paper proposes an efficient algorithm to detect deep communities in the image by maximizing at each stage a new centrality measure, called the local Fiedler vector centrality (LFVC). This measure is associated with the sensitivity of algebraic connectivity to node removals. We show that a greedy node removal strategy, based on iterative maximization of LFVC, has bounded performance loss relative to the optimal, but intractable, combinatorial batch removal strategy. A remarkable feature of this method is the ability to segments the image automatically into homogeneous regions by maximizing…

Centrality in Networks with Overlapping Communities

International audience

Overlapping community detection versus ground-truth in AMAZON co-purchasing network

International audience; Objective evaluation of community detection algorithms is a strategic issue. Indeed, we need to verify that the communities identified are actually the good ones. Moreover, it is necessary to compare results between two distinct algorithms to determine which is most effective. Classically, validations rely on clustering comparison measures or on quality metrics. Although, various traditional performance measures are used extensively. It appears very clearly that they cannot distinguish community structures with different topological properties. It is therefore necessary to propose an alternative methodology more sensitive to the community structure variations in orde…

Color Image Segmentation: The Hypergraph Framework

International audience; Color Image Segmentation: The Hypergraph Framework

On color image quality assessment using natural image statistics

Color distortion can introduce a significant damage in visual quality perception, however, most of existing reduced-reference quality measures are designed for gray scale images. In this paper, we consider a basic extension of well-known image-statistics based quality assessment measures to color images. In order to evaluate the impact of color information on the measures efficiency, two color spaces are investigated: RGB and CIELAB. Results of an extensive evaluation using TID 2013 benchmark demonstrates that significant improvement can be achieved for a great number of distortion type when the CIELAB color representation is used.

Multilayer Network Model of Movie Script

Network models have been increasingly used in the past years to support summarization and analysis of narratives, such as famous TV series, books and news. Inspired by social network analysis, most of these models focus on the characters at play. The network model well captures all characters interactions, giving a broad picture of the narration’s content. A few works went beyond by introducing additional semantic elements, always captured in a single layer network. In contrast, we introduce in this work a multilayer network model to capture more elements of the narration of a movie from its script: people, locations, and other semantic elements. This model enables new measures and insights…

Weighted Adaptive Neighborhood HypergraphPartitioning for Image Segmentation

International audience; The aim of this paper is to present an improvement of a previously published algorithm. The proposed approach is performed in two steps. In the first step, we generate the Weighted Adaptive Neighborhood Hypergraph (WAINH) of the given gray-scale image. In the second step, we partition the WAINH using a multilevel hypergraph partitioning technique. To evaluate the algorithm performances, experiments were carried out on medical and natural images. The results show that the proposed segmentation approach is more accurate than the graph based segmentation algorithm using normalized cut criteria.Key words hypergraph, neighborhood hypergraph, hypergraph partitioning, image…

An empirical investigation of Backbone Filtering Techniques in weighted Complex Networks

Many real-world networks' size and density hinder visualization and graph processing. Several approaches have been developed over the years to reduce the network size while representing the original network as well as possible. "Edge-filtering" techniques focus on removing nodes and edges among the so-called backbone extraction techniques. They can be classified further into "structural" and "statistical". The structural techniques, such as the High-Salience-Skeleton, Doubly-Stochastic Transformation, and the Distance Backbone filter edges according to a criterion allowing the latent structure of the network to emerge. Statistical techniques such as the Disparity Filter, Noise Corrected, an…

A backbone extraction method for complex weighted networks

International audience

Exploring The Mesoscopic Structure Of The World Air Transportation Network

International audience; Air transportation networks have been extensively studied in the network science literature. Researchers focus on airlines networks, national, regional, continental and worldwide networks using monoplex or multiplex approaches. Inspired by recent results on community-aware centrality measures [1], in this work, an extensive analysis of the macroscopic, mesoscopic and microscopic topological properties of the world air transportation network is performed. Based on the community structure uncovered by the Louvain algorithm, the original network is split into local components and global components. The local components are made of the communities by removing the interco…

No-Reference 3D Mesh Quality Assessment Based on Dihedral Angles Model and Support Vector Regression

International audience; 3D meshes are subject to various visual distortions during their transmission and geometrical processing. Several works have tried to evaluate the visual quality using either full reference or reduced reference approaches. However, these approaches require the presence of the reference mesh which is not available in such practical situations. In this paper, the main contribution lies in the design of a computational method to automatically predict the perceived mesh quality without reference and without knowing beforehand the distortion type. Following the no-reference (NR) quality assessment principle, the proposed method focuses only on the distorted mesh. Specific…

A local Agent-Based Model of COVID-19 spreading and interventions

This research presents a simulation model that combines metapopulation geospatial data with the SEIR epidemiological model to simulate a city of up to 250,000 residents while considering various factors such as virus transmission rate, disease severity, and prevention and control measures. This model can assist decision-makers in exploring different pandemic response strategies, including lockdowns, social distancing, mass testing, contact tracing, and vaccination. This simulation aims to provide decision-makers with a better understanding of the implications of their choices and enable them to make informed real-time decisions to manage a health crisis.

An Image Segmentation Algorithm based on Community Detection

International audience; With the recent advances in complex networks, image segmentation becomes one of the most appropriate application areas. In this context, we propose in this paper a new perspective of image segmentation by applying two efficient community detection algorithms. By considering regions as communities, these methods can give an over-segmented image that has many small regions. So, the proposed algorithms are improved to automatically merge those neighboring regions agglomerative to achieve the highest modularity/stability. To produce sizable regions and detect homogeneous communities, we use the combination of a feature based on the Histogram of Oriented Gradients of the …

A stochastic approach for extracting community-based backbones

Large-scale dense networks are very parvasive in various fields such as communication, social analytics, architecture, bio-metrics, etc. Thus, the need to build a compact version of the networks allowing their analysis is a matter of great importance. One of the main solutions to reduce the size of the network while maintaining its characteristics is backbone extraction techniques. Two types of methods are distinguished in the literature: similar nodes are gathered and merged in coarse-graining techniques to compress the network, while filter-based methods discard edges and nodes according to some statistical properties. In this paper, we propose a filtering-based approach which is based on…

M-Centrality: identifying key nodes based on global position and local degree variation

Identifying influential nodes in a network is a major issue due to the great deal of applications concerned, such as disease spreading and rumor dynamics. That is why, a plethora of centrality measures has emerged over the years in order to rank nodes according to their topological importance in the network. Local metrics such as degree centrality make use of a very limited information and are easy to compute. Global metrics such as betweenness centrality exploit the information of the whole network structure at the cost of a very high computational complexity. Recent works have shown that combining multiple metrics is a promising strategy to quantify the node's influential ability. Our wor…

A convolutional neural network framework for blind mesh visual quality assessment

In this paper, we propose a new method for blind mesh visual quality assessment using a deep learning approach. To do this, we first extract visual representative features by computing locally curvature and dihedral angles from each distorted mesh. Then, we determine from these features a set of 2D patches which are learned to a convolutional neural network (CNN). The network consists of two convolutional layers with two max-pooling layers. Then, a multilayer perceptron (MLP) with two fully connected layers is integrated to summarize the learned representation into an output node. With this network structure, feature learning and regression are used to predict the quality score of a given d…

3d mesh denoising using normal based myriad filter

We propose a new filtering scheme for denoising of 3D objects which are represented by a triangular mesh. This scheme consists on applying myriad filter to face normals and then updating the vertices positions in order to preserve the original shape of the object. The choice of the Myriad is justified by the assumption of Cauchy distributed angles between surface normals. This filter improves the performance of a normal-based method which is adapted to the underlying mesh structure. To evaluate these methods of filtering, we use three error metrics. The first is based on the vertices, the second is based on the normals and the third is based on Hausdorff distance. Experimental results demon…

A robust blind 3-D mesh watermarking based on wavelet transform for copyright protection

Nowadays, three-dimensional meshes have been extensively used in several applications such as, industrial, medical, computer-aided design (CAD) and entertainment due to the processing capability improvement of computers and the development of the network infrastructure. Unfortunately, like digital images and videos, 3-D meshes can be easily modified, duplicated and redistributed by unauthorized users. Digital watermarking came up while trying to solve this problem. In this paper, we propose a blind robust watermarking scheme for three-dimensional semiregular meshes for Copyright protection. The watermark is embedded by modifying the norm of the wavelet coefficient vectors associated with th…

Evaluating Community Detection Algorithms: A multidimensional issue

International audience; na

A Sentiment Enhanced Deep Collaborative Filtering Recommender System

Recommender systems use advanced analytic and learning techniques to select relevant information from massive data and inform users’ smart decision-making on their daily needs. Numerous works exploiting user’s sentiments on products to enhance recommendations have been introduced. However, there has been relatively less work exploring higher-order user-item features interactions for sentiment enhanced recommender system. In this paper, a novel Sentiment Enhanced Deep Collaborative Filtering Recommender System (SE-DCF) is developed. The architecture is based on a Neural Attention network component aggregated with the output predictions of a Convolution Neural Network (CNN) recommender. Speci…

Application of Adaptive Hypergraph Model to Impulsive Noise Detection

In this paper, using hypergraph theory, we introduce an image model called Adaptive Image Neighborhood Hypergraph (AINH). From this model we propose a combinatorial definition of noisy data. A detection procedure is used to classify the hyperedges either as noisy or clean data. Similar to other techniques, the proposed algorithm uses an estimation procedure to remove the effects of the noise. Extensive simulations show that the proposed scheme consistently works well in suppressing of impulsive noise.

Tetrolet-based reduced reference image quality assessment approach

In this paper, we propose a new reduced reference image quality assessment (RRIQA) scheme. For this purpose, we use a statistical-based method in a new adaptive Haar wavelet transform domain, called Tetrolet. Firstly, we decompose the reference and distorted images and we obtain the Tetrolet coefficients for each image. Secondly, we use a marginal Generalized Gaussian Density (GGD) to model each subband coefficients. Finally, the distortion measure is computed using the Kullback Leibler Divergence (KLD) between GGD Probability density function (PDFs). Experimental results show the efficiency of the proposed method when comparing to those reported in the literature.

Effect of Topological Structure and Coupling Strength in Weighted Multiplex Networks

Algebraic connectivity (second smallest eigenvalue of the supra-Laplacian matrix of the underlying multilayer network) and inter-layer coupling strength play an important role in the diffusion processes on the multiplex networks. In this work, we study the effect of inter-layer coupling strength, topological structure on algebraic connectivity in weighted multiplex networks. The results show a remarkable transition in the value of algebraic connectivity from classical cases where the inter-layer coupling strength is homogeneous. We investigate various topological structures in multiplex networks using configuration model, the Barabasi-Albert model (BA) and empirical data-set of multiplex ne…

k-Truss Decomposition for Modular Centrality

There is currently much interest in identifying influential spreaders in complex networks due to many applications concerned, such as controlling the outbreak of epidemics and conducting advertisements for commercial products, and so on. A plethora of centrality measures have been proposed over the years based on the topological properties of networks. However, most of these classical centrality measures fail to select the most influential nodes in networks with a modular structure despite that it is an omnipresent property in real-world networks. Few authors have introduced centrality measures tailored to networks with community structure. In a recent work, we have shown that, in this case…

Community-based Immunization Strategies for Epidemic Control

Understanding the epidemic dynamics, and finding out efficient techniques to control it, is a challenging issue. A lot of research has been done on targeted immunization strategies, exploiting various global network topological properties. However, in practice, information about the global structure of the contact network may not be available. Therefore, immunization strategies that can deal with a limited knowledge of the network structure are required. In this paper, we propose targeted immunization strategies that require information only at the community level. Results of our investigations on the SIR epidemiological model, using a realistic synthetic benchmark with controlled community…

A Combinatorial Color Edge Detector

In this paper, we present an edge detection approach in color image using neighborhood hypergraph. The edge structure is detected by a structural model. The Color Image Neighborhood Hypergraph (CINH) representation is first computed, then the hyperedges of CINH are classified into noise or edge based on hypergraph properties. To evaluate the algorithm performance, experiments were carried out on synthetic and real color images corrupted by alpha-stable noise. The results show that the proposed edge detector finds the edges properly from color images.

A new image segmentation approach using community detection algorithms

Image segmentation has an important role in many image processing applications. Several methods exist for segmenting an image. However, this technique is still a relatively open topic for which various research works are regularly presented. With the recent developments on complex networks theory, image segmentation techniques based on graphs has considerably improved. In this paper, we present a new perspective of image segmentation, by applying three of the most efficient community detection algorithms, Louvain, infomap and stability optimization based on the louvain algorithm, and we extract communities in which the highest modularity feature is achieved. After we show that this measure …

A Multi-Layer Network Model of Climate Reinsurance: Company Benefits vs. Climate Resilience?

The global (re)insurance market faces a limited capacity to absorb risk, particularly in areas with increasing climate risks. Only four companies dominate the market. It indicates the possibility of oligopoly limiting the market's capacity to absorb climate risks. Traditional economic models fail to consider the influence of market structures, which we capture in a multilayer network model. The model reflects the activities of public and private entities with insurance cover, primary insurers, and re-insurers, represented as nodes forming multiple layers. To understand the impact of higher levels of risk related to a changing climate, we investigate the risk transfer and claim activation co…

A Robust Blind 3-D Mesh Watermarking Technique Based on SCS Quantization and Mesh Saliency for Copyright Protection

Due to the recent demand of 3-D meshes in a wide range of applications such as video games, medical imaging, film special effect making, computer-aided design (CAD), among others, the necessity of implementing 3-D mesh watermarking schemes aiming to protect copyright has increased in the last decade. Nowadays, the majority of robust 3-D watermarking approaches have mainly focused on the robustness against attacks while the imperceptibility of these techniques is still a serious challenge. In this context, a blind robust 3-D mesh watermarking method based on mesh saliency and scalar Costa scheme (SCS) for Copyright protection is proposed. The watermark is embedded by quantifying the vertex n…

Hypergraph imaging: an overview

Hypergraph theory as originally developed by Berge (Hypergraphe, Dunod, Paris, 1987) is a theory of finite combinatorial sets, modeling lot of problems of operational research and combinatorial optimization. This framework turns out to be very interesting for many other applications, in particular for computer vision. In this paper, we are going to survey the relationship between combinatorial sets and image processing. More precisely, we propose an overview of different applications from image hypergraph models to image analysis. It mainly focuses on the combinatorial representation of an image and shows the effectiveness of this approach to low level image processing; in particular to seg…

NetBone: A Python Package for Extracting Backbones of Weighted Networks

NetBone is a new open-source Python package designed to simplify analyzing complex networks. With a wide range of techniques available, Net-Bone allows researchers to extract the backbone of a network while preserving its essential structure. The package includes nine structural methods and five statistical techniques, offering users a comprehensive solution to network analysis. It is user-friendly and straightforward to use, with easy installation. The package accepts different types of inputs, including data frames or Networkx graphs, and provides evaluation measures for comparative purposes. Additionally, NetBone offers an option to generate plots. Its versatility makes it a valuable too…

Parallel filter estimation algorithm for segmentation on a LAN of workstations

International audience

Assessing the Relationship Between Centrality and Hierarchy in Complex Networks

International audience

Investigating Centrality Measures in Social Networks with Community Structure

Centrality measures are crucial in quantifying the influence of the members of a social network. Although there has been a great deal of work dealing with this issue, the vast majority of classical centrality measures are agnostic of the community structure characterizing many social networks. Recent works have developed community-aware centrality measures that exploit features of the community structure information encountered in most real-world complex networks. In this paper, we investigate the interactions between 5 popular classical centrality measures and 5 community-aware centrality measures using 8 real-world online networks. Correlation as well as similarity measures between both t…

Mesh Visual Quality based on the combination of convolutional neural networks

Blind quality assessment is a challenging issue since the evaluation is done without access to the reference nor any information about the distortion. In this work, we propose an objective blind method for the visual quality assessment of 3D meshes. The method estimates the perceived visual quality using only information from the distorted mesh to feed pre-trained deep convolutional neural networks. The input data is prepared by rendering 2D views from the 3D mesh and the corresponding saliency map. The views are split into small patches of fixed size that are filtered using a saliency threshold. Only the salient patches are selected as input data. After that, three pre-trained deep convolu…

Classical versus Community-aware Centrality Measures: An Empirical Study

International audience

A new weighted normal-based filter for 3D mesh denoising

In this paper, we propose a normal based filtering method for 3D mesh denoising. For this purpose, we compute the new triangle normal vectors by using a weighted sum of the average (smoothness) and the myriad (sharpness) filters in each neighborhood. These weights, that reflect the degree of the surface sharpness, are calculated according to the statistical distribution of the angles between the normal vectors of the triangles. The histogram of the angles between surface normal vectors is accurately fitted by the well known Cauchy distribution. Here, we justify the use of the myriad filter whose estimated value represents the optimum of the location parameter of the investigated distributio…

Context-Awareness in Ensemble Recommender System Framework

Recommender systems that provide recommendations based uniquely on information over users and items may not be very accurate in some situations. Therefore, adding contextual information to recommendations may be a good choice resulting in a system with increased precision. In an early work, we proposed an Ensemble Variational Autoencoders (EnsVAE) framework for recommendation. EnsVAE is adjusted to output interest probabilities by learning the distribution of each item's ratings and attempts to provide diverse novel items that are pertinent to users. In this paper, we propose and investigate a context awareness framework based on the Ensemblist Variational Autoencoders model with integratin…

Extracting Backbones in Weighted Modular Complex Networks

AbstractNetwork science provides effective tools to model and analyze complex systems. However, the increasing size of real-world networks becomes a major hurdle in order to understand their structure and topological features. Therefore, mapping the original network into a smaller one while preserving its information is an important issue. Extracting the so-called backbone of a network is a very challenging problem that is generally handled either by coarse-graining or filter-based methods. Coarse-graining methods reduce the network size by grouping similar nodes, while filter-based methods prune the network by discarding nodes or edges based on a statistical property. In this paper, we pro…

Analysis of the German Commuter Network Period 2013 -2021

Understanding the behavior of commuters is crucial as the number of commuters steadily rises, causing significant traffic congestion in many cities. Indeed, commuter behavior is vital in city and transport planning and policy-making. Previous studies have investigated various factors that may impact commuting decisions. Still, these studies are often limited by the scale of data examined, including time duration, space, and the number of commuters. To address this gap, we gathered large-scale inter-city commuting data in Germany and analyzed the weighted commuting network from 2013 to 2021. This work relies on publicly available data so that the results can be reproduced.

No-reference mesh visual quality assessment via ensemble of convolutional neural networks and compact multi-linear pooling

Abstract Blind or No reference quality evaluation is a challenging issue since it is done without access to the original content. In this work, we propose a method based on deep learning for the mesh visual quality assessment without reference. For a given 3D model, we first compute its mesh saliency. Then, we extract views from the 3D mesh and the corresponding mesh saliency. After that, the views are split into small patches that are filtered using a saliency threshold. Only the salient patches are selected and used as input data. After that, three pre-trained deep convolutional neural networks are employed for feature learning: VGG, AlexNet, and ResNet. Each network is fine-tuned and pro…

A blind mesh visual quality assessment method based on convolutional neural network

International audience

Centrality in Complex Networks with Overlapping Community Structure

AbstractIdentifying influential spreaders in networks is an essential issue in order to prevent epidemic spreading, or to accelerate information diffusion. Several centrality measures take advantage of various network topological properties to quantify the notion of influence. However, the vast majority of works ignore its community structure while it is one of the main features of many real-world networks. In a recent study, we show that the centrality of a node in a network with non-overlapping communities depends on two features: Its local influence on the nodes belonging to its community, and its global influence on the nodes belonging to the other communities. Using global and local co…

An Empirical Study of the Relation Between Community Structure and Transitivity

One of the most prominent properties in real-world networks is the presence of a community structure, i.e. dense and loosely interconnected groups of nodes called communities. In an attempt to better understand this concept, we study the relationship between the strength of the community structure and the network transitivity (or clustering coefficient). Although intuitively appealing, this analysis was not performed before. We adopt an approach based on random models to empirically study how one property varies depending on the other. It turns out the transitivity increases with the community structure strength, and is also affected by the distribution of the community sizes. Furthermore, …

Image Quality Assessment Measure Based on Natural Image Statistics in the Tetrolet Domain

This paper deals with a reduced reference (RR) image quality measure based on natural image statistics modeling. For this purpose, Tetrolet transform is used since it provides a convenient way to capture local geometric structures. This transform is applied to both reference and distorted images. Then, Gaussian Scale Mixture (GSM) is proposed to model subbands in order to take account statistical dependencies between tetrolet coefficients. In order to quantify the visual degradation, a measure based on Kullback Leibler Divergence (KLD) is provided. The proposed measure was tested on the Cornell VCL A-57 dataset and compared with other measures according to FR-TV1 VQEG framework.

Neighborhood Hypergraph Partitioning for Image Segmentation

International audience; The aim of this paper is to introduce a multilevel neighborhoodhypergraph partitioning for image segmentation. Our proposedapproach uses the image neighborhood hypergraph model introduced inour last works and the algorithm of multilevel hypergraphpartitioning introduced by George Karypis. To evaluate the algorithmperformance, experiments were carried out on a group of gray scaleimages. The results show that the proposed segmentation approachfind the region properly from images as compared to imagesegmentation algorithm using normalized cut criteria.Key words :Graph, Hypergraph, Neighborhood hypergraph, multilevel hypergraph partitioning, image segmentation, edge dete…

Special issue on the occasion of the International Workshop on Complex Networks and their Applications

Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure

International audience; Understanding how the network topology affects the spread of an epidemic is a main concern in order to develop efficient immunization strategies. While there is a great deal of work dealing with the macroscopic topological properties of the networks, few studies have been devoted to the influence of the community structure. Furthermore, while in many real-world networks communities may overlap, in these studies non-overlapping community structures are considered. In order to gain insight about the influence of the overlapping nodes in the epidemic process we conduct an empirical evaluation of basic deterministic immunization strategies based on the overlapping nodes.…

Mesh Visual Quality Assessment Metrics: A Comparison Study

3D graphics technologies have known a developed progress in the last years, and several processing operations can be applied on 3D meshes such as watermarking, compression, simplification and so forth. Mesh visual quality assessment becomes an important issue to evaluate the visual appearance of the 3D shape after specific modifications. Several metrics have been proposed in this context, from the classical distance-based metrics to the perceptual-based metrics which include perceptual information about the human visual system. In this paper, we propose to study the performance of several mesh visual quality metrics. First, the comparison is conducted regardless the distortion types neither…

Betweenness Centrality for Networks with Non-Overlapping Community Structure

Evaluating the centrality of nodes in complex networks is one of the major research topics being explored due to its wide range of applications. Among the various measures that have been developed over the years, Betweenness centrality is one of the most popular. Indeed, it has proved to be efficient in many real-world situations. In this paper, we propose an extension of the Betweenness centrality designed for networks with nonoverlapping community structure. It is a linear combination of the so-called “local” and “global” Betweenness measures. The Local measure takes into account the influence of a node at the community level while the global measure depends only on the interactions betwe…

Multilayer Network Model of Movie Script

Network models have been increasingly used in the past years to support summarization and analysis of narratives, such as famous TV series, books and news. Inspired by social network analysis, most of these models focus on the characters at play. The network model well captures all characters interactions, giving a broad picture of the narration's content. A few works went beyond by introducing additional semantic elements, always captured in a single layer network. In contrast, we introduce in this work a multilayer network model to capture more elements of the narration of a movie from its script: people, locations, and other semantic elements. This model enables new measures and insights…

A Comparison of Model-Based Backbone Filtering Techniques in the Air Transportation Network

Localization of hubs in complex networks with overlapping modular structure

International audience

Interactions between overlapping nodes and hubs in complex networks with modular structure

International audience

An Agent based model for the transmission and control of the COVID-19 in Dijon

International audience

Reduced reference 3D mesh quality assessment based on statistical models

International audience; During their geometry processing and transmission 3D meshes are subject to various visual processing operations like compression, watermarking, remeshing, noise addition and so forth. In this context it is indispensable to evaluate the quality of the distorted mesh, we talk here about the mesh visual quality (MVQ) assessment. Several works have tried to evaluate the MVQ using simple geometric measures, However this metrics do not correlate well with the subjective score since they fail to reflect the perceived quality. In this paper we propose a new objective metric to evaluate the visual quality between a mesh with a perfect quality called reference mesh and its dis…

Optimal Local Routing Strategies for Community Structured Time Varying Communication Networks

International audience; In time varying data communication networks (TVCN), traffic congestion, system utility maximization and network performance enhancement are the prominent issues. All these issues can be resolved either by optimizing the network structure or by selecting efficient routing approaches. In this paper, we focus on the design of a time varying network model and propose an algorithm to find efficient user route in this network. Centrality plays a very important role in finding congestion free routes. Indeed, the more a node is central, the more it can be congested by the flow coming from or going to its neighborhood. For that reason, classically, routes are chosen such that…

Comparative Evaluation of Community Detection Algorithms: A Topological Approach

International audience; Community detection is one of the most active fields in complex networks analysis, due to its potential value in practical applications. Many works inspired by different paradigms are devoted to the development of algorithmic solutions allowing to reveal the network structure in such cohesive subgroups. Comparative studies reported in the literature usually rely on a performance measure considering the community structure as a partition (Rand Index, Normalized Mutual information, etc.). However, this type of comparison neglects the topological properties of the communities. In this article, we present a comprehensive comparative study of a representative set of commu…

Convolutional Neural Network for Blind Mesh Visual Quality Assessment Using 3D Visual Saliency

International audience

Combination Of Handcrafted And Deep Learning-Based Features For 3d Mesh Quality Assessment

We propose in this paper a novel objective method to evaluate the perceived visual quality of 3D meshes. The proposed method in no-reference, it relies only on the distorted mesh for the quality estimation. It is based on a pre-trained convolutional neural network (i.e VGG to extract features from the distorted mesh) and handcrafted features extracted directly from the 3D mesh (i.e curvature and dihedral angle). A General Regression Neural Network (GRNN) is used to learn the statistical parameters of the feature vectors and estimate the quality score. Experimental results from for subjective databases (LIRIS masking, LIRIS/EPFL generalpurpose, UWB compression and LEETA simplification) and c…

Hierarchy and Centrality: Two Sides of The Same Coin?

International audience

On local and global components of the air transportation network

International audience

Maximum likelihood difference scaling of image quality in compression-degraded images.

International audience; Lossy image compression techniques allow arbitrarily high compression rates but at the price of poor image quality. We applied maximum likelihood difference scaling to evaluate image quality of nine images, each compressed via vector quantization to ten different levels, within two different color spaces, RGB and CIE 1976 L(*)a(*)b(*). In L(*)a(*)b(*) space, images could be compressed on average by 32% more than in RGB space, with little additional loss in quality. Further compression led to marked perceptual changes. Our approach permits a rapid, direct measurement of the consequences of image compression for human observers.

Hybrid blind robust image watermarking technique based on DFT-DCT and Arnold transform

In this paper, a robust blind image watermarking method is proposed for copyright protection of digital images. This hybrid method relies on combining two well-known transforms that are the discrete Fourier transform (DFT) and the discrete cosine transform (DCT). The motivation behind this combination is to enhance the imperceptibility and the robustness. The imperceptibility requirement is achieved by using magnitudes of DFT coefficients while the robustness improvement is ensured by applying DCT to the DFT coefficients magnitude. The watermark is embedded by modifying the coefficients of the middle band of the DCT using a secret key. The security of the proposed method is enhanced by appl…

Editorial special issue on Community structure in complex networks

Analyse de la robustesse du réseau de transport aérien mondial : impact sur sa structure en composante

The Footprints of a “Mastodon”: How a Decentralized Architecture Influences Online Social Relationships

Decentralized online social networks (DOSNs) have recently emerged as a viable solution to preserve the users' privacy and ensure higher users' control over the contents they publish. However, little is known about the backlashes that the decentralized organization and management of these platforms may have on the overlaid social network. This paper fills the gap. Specifically, we investigate how a decentralized architecture based on distributed servers impacts the structure of the users' neighborhood and their ego-networks. Our analysis relies on social data gathered from the decentralized micro-blogging platform Mastodon, the newest and fastest-growing decentralized alternative to Twitter…

Color image quality assessment measure using multivariate generalized Gaussian distribution

This paper deals with color image quality assessment in the reduced-reference framework based on natural scenes statistics. In this context, we propose to model the statistics of the steer able pyramid coefficients by a Multivariate Generalized Gaussian distribution (MGGD). This model allows taking into account the high correlation between the components of the RGB color space. For each selected scale and orientation, we extract a parameter matrix from the three color components sub bands. In order to quantify the visual degradation, we use a closed-form of Kullback-Leibler Divergence (KLD) between two MGGDs. Using "TID 2008" benchmark, the proposed measure has been compared with the most i…