MmWave Physical Layer Network Modeling and Planning for Fixed Wireless Access Applications.

The large bandwidths that are available at millimeter-wave frequencies enable fixed wireless access (FWA) applications, in which fixed point-to-point wireless links are used to provide internet connectivity. In FWA networks, a wireless mesh is created and data are routed from the customer premises equipment (CPE) towards the point of presence (POP), which is the interface with the wired internet infrastructure. The performance of the wireless links depends on the radio propagation characteristics, as well as the wireless technology that is used. The radio propagation characteristics depend on the environment and on the considered frequency. In this work, we analyzed the network characteristics of FWA networks using radio propagation models for different wireless technologies using millimeter-wave (mmWave) frequencies of 28 GHz, 60 GHz, and 140 GHz. Different scenarios and environments were considered, and the influence of rain, vegetation, and the number of subscribers was investigated. A network planning algorithm is presented that defines a route for each CPE towards the POP based on a predefined location of customer devices and considering the available capacity of the wireless links. Rain does not have a considerable effect on the system capacity. Even though the higher frequencies exhibit a larger path loss, resulting in a lower power of the received signal, the larger bandwidths enable a higher channel capacity.

A construction heuristic for the capacitated Steiner tree problem.

Many real-life problems boil down to a variant of the Minimum Steiner Tree Problem (STP). In telecommunications, Fiber-To-The-Home (FTTH) houses are clustered so they can be connected with fiber as cost-efficiently as possible. The cost calculation of a fiber installment can be formulated as a capacitated STP. Often, STP variants are solved with integer linear programs, which provide excellent solutions, though the running time costs increase quickly with graph size. Some geographical areas require graphs of over 20000 nodes-typically unattainable for integer linear programs. This paper presents an alternative approach. It extends the shortest path heuristic for the STP to a new heuristic that can construct solutions for the capacitated STP: the Capacitated Shortest Path Heuristic (CSPH). It is straightforward to implement, allowing many extensions. In experiments on realistic telecommunications datasets, CSPH finds solutions on average in time O(|V|2), quadratic in the number of nodes, making it possible to solve 50000 node graphs in under a minute.

Optimising orbit counting of arbitrary order by equation selection.

BACKGROUND: Graphlets are useful for bioinformatics network analysis. Based on the structure of Hocevar and Demsar's ORCA algorithm, we have created an orbit counting algorithm, named Jesse. This algorithm, like ORCA, uses equations to count the orbits, but unlike ORCA it can count graphlets of any order. To do so, it generates the required internal structures and equations automatically. Many more redundant equations are generated, however, and Jesse's running time is highly dependent on which of these equations are used. Therefore, this paper aims to investigate which equations are most efficient, and which factors have an effect on this efficiency. RESULTS: With appropriate equation selection, Jesse's running time may be reduced by a factor of up to 2 in the best case, compared to using randomly selected equations. Which equations are most efficient depends on the density of the graph, but barely on the graph type. At low graph density, equations with terms in their right-hand side with few arguments are more efficient, whereas at high density, equations with terms with many arguments in the right-hand side are most efficient. At a density between 0.6 and 0.7, both types of equations are about equally efficient. CONCLUSIONS: Our Jesse algorithm became up to a factor 2 more efficient, by automatically selecting the best equations based on graph density. It was adapted into a Cytoscape App that is freely available from the Cytoscape App Store to ease application by bioinformaticians.

Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations.

Motivation: Graphlets are a useful tool to determine a graph's small-scale structure. Finding them is exponentially hard with respect to the number of nodes in each graphlet. Therefore, equations can be used to reduce the size of graphlets that need to be enumerated to calculate the number of each graphlet touching each node. Hocevar and Demsar first introduced such equations, which were derived manually, and an algorithm that uses them, but only graphlets with four or five nodes can be counted this way. Results: We present a new algorithm for orbit counting, which is applicable to graphlets of any order. This algorithm uses a tree structure to simplify finding orbits, and stabilizers and symmetry-breaking constraints to ensure correctness. This method gives a significant speedup compared to a brute force counting method and can count orbits beyond the capacity of other available tools. Availability and implementation: An implementation of the algorithm can be found at https://github.com/biointec/jesse. Contact: pieter.audenaert@ugent.be.

A Cytoscape app for motif enumeration with ISMAGS.

Summary: We present a Cytoscape app for the ISMAGS algorithm, which can enumerate all instances of a motif in a graph, making optimal use of the motif's symmetries to make the search more efficient. The Cytoscape app provides a handy interface for this algorithm, which allows more efficient network analysis. Availability and Implementation: The Cytoscape app for ISMAGS can be freely downloaded from the Cytoscape App store http://apps.cytoscape.org/apps/ismags. Source code and documentation for ISMAGS are available at https://github.com/biointec/ismags. Source code and documentation for the Cytoscape app are available at https://gitlab.psb.ugent.be/thpar/ISMAGS_Cytoscape. Contacts: Pieter.Audenaert@intec.ugent.be or Yves.VanDePeer@psb.vib-ugent.be Supplementary information: Supplementary data are available at Bioinformatics online.

An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations.

Graphlets are small subgraphs, usually containing up to five vertices, that can be found in a larger graph. Identification of the graphlets that a vertex in an explored graph touches can provide useful information about the local structure of the graph around that vertex. Actually finding all graphlets in a large graph can be time-consuming, however. As the graphlets grow in size, more different graphlets emerge and the time needed to find each graphlet also scales up. If it is not needed to find each instance of each graphlet, but knowing the number of graphlets touching each node of the graph suffices, the problem is less hard. Previous research shows a way to simplify counting the graphlets: instead of looking for the graphlets needed, smaller graphlets are searched, as well as the number of common neighbors of vertices. Solving a system of equations then gives the number of times a vertex is part of each graphlet of the desired size. However, until now, equations only exist to count graphlets with 4 or 5 nodes. In this paper, two new techniques are presented. The first allows to generate the equations needed in an automatic way. This eliminates the tedious work needed to do so manually each time an extra node is added to the graphlets. The technique is independent on the number of nodes in the graphlets and can thus be used to count larger graphlets than previously possible. The second technique gives all graphlets a unique ordering which is easily extended to name graphlets of any size. Both techniques were used to generate equations to count graphlets with 4, 5 and 6 vertices, which extends all previous results. Code can be found at https://github.com/IneMelckenbeeck/equation-generator and https://github.com/IneMelckenbeeck/graphlet-naming.

The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.

Subgraph matching algorithms are used to find and enumerate specific interconnection structures in networks. By enumerating these specific structures/subgraphs, the fundamental properties of the network can be derived. More specifically in biological networks, subgraph matching algorithms are used to discover network motifs, specific patterns occurring more often than expected by chance. Finding these network motifs yields information on the underlying biological relations modelled by the network. In this work, we present the Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS), an improved version of the Index-based Subgraph Matching Algorithm (ISMA). ISMA quickly finds all instances of a predefined motif in a network by intelligently exploring the search space and taking into account easily identifiable symmetric structures. However, more complex symmetries (possibly involving switching multiple nodes) are not taken into account, resulting in superfluous output. ISMAGS overcomes this problem by using a customised symmetry analysis phase to detect all symmetric structures in the network motif subgraphs. These structures are then converted to symmetry-breaking constraints used to prune the search space and speed up calculations. The performance of the algorithm was tested on several types of networks (biological, social and computer networks) for various subgraphs with a varying degree of symmetry. For subgraphs with complex (multi-node) symmetric structures, high speed-up factors are obtained as the search space is pruned by the symmetry-breaking constraints. For subgraphs with no or simple symmetric structures, ISMAGS still reduces computation times by optimising set operations. Moreover, the calculated list of subgraph instances is minimal as it contains no instances that differ by only a subgraph symmetry. An implementation of the algorithm is freely available at https://github.com/mhoubraken/ISMAGS.

The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.

Subgraph matching algorithms are designed to find all instances of predefined subgraphs in a large graph or network and play an important role in the discovery and analysis of so-called network motifs, subgraph patterns which occur more often than expected by chance. We present the index-based subgraph matching algorithm (ISMA), a novel tree-based algorithm. ISMA realizes a speedup compared to existing algorithms by carefully selecting the order in which the nodes of a query subgraph are investigated. In order to achieve this, we developed a number of data structures and maximally exploited symmetry characteristics of the subgraph. We compared ISMA to a naive recursive tree-based algorithm and to a number of well-known subgraph matching algorithms. Our algorithm outperforms the other algorithms, especially on large networks and with large query subgraphs. An implementation of ISMA in Java is freely available at http://sourceforge.net/projects/isma/.

Worldwide electricity consumption of communication networks.

There is a growing research interest in improving the energy efficiency of communication networks. In order to assess the impact of introducing new energy efficient technologies, an up-to-date estimate for the global electricity consumption in communication networks is needed. In this paper we consider the use phase electricity consumption of telecom operator networks, office networks and customer premises equipment. Our results show that the network electricity consumption is growing fast, at a rate of 10 % per year, and its relative contribution to the total worldwide electricity consumption has increased from 1.3% in 2007 to 1.8% in 2012. We estimate the worldwide electricity consumption of communication networks will exceed 350 TWh in 2012.

ONU power saving modes in next generation optical access networks: progress, efficiency and challenges.

The optical network unit (ONU), installed at a customer's premises, accounts for about 60% of power in current fiber-to-the-home (FTTH) networks. We propose a power consumption model for the ONU and evaluate the ONU power consumption in various next generation optical access (NGOA) architectures. Further, we study the impact of the power savings of the ONU in various low power modes such as power shedding, doze and sleep.

CyClus3D: a Cytoscape plugin for clustering network motifs in integrated networks.

SUMMARY: Network motifs in integrated molecular networks represent functional relationships between distinct data types. They aggregate to form dense topological structures corresponding to functional modules which cannot be detected by traditional graph clustering algorithms. We developed CyClus3D, a Cytoscape plugin for clustering composite three-node network motifs using a 3D spectral clustering algorithm. AVAILABILITY: Via the Cytoscape plugin manager or http://bioinformatics.psb.ugent.be/software/details/CyClus3D.