Search

The backbone extraction process is pivotal in expediting analysis and enhancing visualization in network applications. This study systematically compares seven influential statistical hypothesis-testing backbone edge filtering methods (Disparity Filter (DF), Polya Urn Filter (PF), Marginal Likelihood Filter (MLF), Noise Corrected (NC), Enhanced Configuration Model Filter (ECM), Global Statistical Significance Filter (GloSS), and Locally Adaptive Network Sparsification Filter (LANS)) across diverse networks. A similarity analysis reveals that backbones extracted with the ECM and DF filters exhibit minimal overlap with backbones derived from their alternatives. Interestingly, ordering the other methods from GloSS to NC, PF, LANS, and MLF, we observe that each method's output encapsulates the backbone of the previous one. Correlation analysis between edge features (weight, degree, betweenness) and the test significance level reveals that the DF and LANS filters favor high-weighted edges while ECM assigns them lower significance to edges with high degrees. Furthermore, the results suggest a limited influence of the edge betweenness on the filtering process. The backbones global properties analysis (edge fraction, node fraction, weight fraction, weight entropy, reachability, number of components, and transitivity) identifies three typical behavior types for each property. Notably, the LANS filter preserves all nodes and weight entropy. In contrast, DF, PF, ECM, and GloSS significantly reduce network size. The MLF, NC, and ECM filters preserve network connectivity and weight entropy. Distribution analysis highlights the PU filter's ability to capture the original weight distribution. NC filter closely exhibits a similar capability. NC and MLF filters excel for degree distribution. These insights offer valuable guidance for selecting appropriate backbone extraction methods based on specific properties.

Abstract Networks are essential for analyzing complex systems. However, their growing size necessitates backbone extraction techniques aimed at reducing their size while retaining critical features. In practice, selecting, implementing, and evaluating the most suitable backbone extraction method may be challenging. This paper introduces netbone, a Python package designed for assessing the performance of backbone extraction techniques in weighted networks. Its comparison framework is the standout feature of netbone. Indeed, the tool incorporates state-of-the-art backbone extraction techniques. Furthermore, it provides a comprehensive suite of evaluation metrics allowing users to evaluate different backbones techniques. We illustrate the flexibility and effectiveness of netbone through the US air transportation network analysis. We compare the performance of different backbone extraction techniques using the evaluation metrics. We also show how users can integrate a new backbone extraction method into the comparison framework. netbone is publicly available as an open-source tool, ensuring its accessibility to researchers and practitioners. Promoting standardized evaluation practices contributes to the advancement of backbone extraction techniques and fosters reproducibility and comparability in research efforts. We anticipate that netbone will serve as a valuable resource for researchers and practitioners enabling them to make informed decisions when selecting backbone extraction techniques to gain insights into the structural and functional properties of complex systems.

Inspired by the split decomposition of graphs and rank-width, we introduce the notion of $r$-splits. We focus on the family of $r$-splits of a graph of order $n$, and we prove that it forms a hypergraph with several properties. We prove that such hypergraphs can be represented using only $\mathcal O(n^{r+1})$ of its hyperedges, despite its potentially exponential number of hyperedges. We also prove that there exist hypergraphs that need at least $\Omega(n^r)$ hyperedges to be represented, using a generalization of set orthogonality.

Abstract The way nodes are arranged in a wireless network can significantly influence performance, especially information flow. The construction of disjoint virtual backbone networks (DVBNs) is one of the ways this can be accomplished. In this study, the authors first present a proposal that constructs multiple DVBNs using nodes' locations, in two phases. In the second phase of the proposal, dominator selection is initiated by the sink and then continued by each selected dominator. This occurs in rounds, with each round producing a distinct virtual backbone. The simulations show that multiple DVBNs can be produced with a good approximation ratio. Further, two optimisations are presented, one for a scanty network and the other for data dissemination. These are accomplished by changing the way in which the dominators are selected in the second phase of the algorithm. These optimisations are evaluated and a marked improvement is observed in node connectedness to the backbone and in hop count while keeping approximation ratios almost constant.

Providing Internet of Things (IoT) environments with service level guarantee is a challenging task for improving IoT application usage experience. We specify in this paper an IoT architecture enabling an IoT Service Level Agreement (iSLA) achievement between an IoT Service Provider (IoT-SP) and an IoT Client (IoT-C). In order to guarantee the IoT applications’ requirements, Quality of Service (QoS) mechanisms should be implemented within all the layers of the IoT architecture. Thus, we propose a specific mechanism for the lowest layer of our service level based IoT architecture (i.e., sensing layer). It is an adaptation of the IEEE 802.15.4 slotted CSMA/CA mechanism enabling to take into consideration the requirements of real-time IoT services. Our access method called QBAIoT (QoS based Access for IoT) extends IEEE 802.15.4 systems by creating a new contention access period for each specified traffic class in the iSLA. Furthermore, due to the huge number of IoT connected devices, self-configuring capability provisioning is necessary for limiting human intervention and total cost of ownership (TCO). Thus, we integrate a self-configuring capability to the QBAIoT access method by implementing the MAPE-K closed control loop within the IoT High Level Gateway (HL-Gw) of our proposed QoS based IoT architecture.

For a set D⊂ Z n, the distance graph P n (D) has Z n as its vertex set and the edges are between vertices i and j with |i-j|∈D. The circulant graph C n (D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.

Graphs and Algorithms

The strong chromatic index of a graph is the minimum number of colours needed to colour the edges in such a way that each colour class is an induced matching. In this paper, we present bounds for strong chromatic index of three different products of graphs in term of the strong chromatic index of each factor. For the cartesian product of paths, cycles or complete graphs, we derive sharper results. In particular, strong chromatic indices of d-dimensional grids and of some toroidal grids are given along with approximate results on the strong chromatic index of generalized hypercubes.

A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infinite triangular mesh is an induced subgraph of the fourth power of the infinite square mesh and we present 2-approximation algorithms for multicoloring a power square mesh and the second power of a triangular mesh, 3-approximation algorithms for multicoloring powers of semi-toroidal meshes and of triangular meshes and 4-approximation algorithm for multicoloring the power of a toroidal mesh. We also give similar algorithms for the Cartesian product of powers of paths and of cycles.