document

The Union of Shortest Path Trees of Functional Brain Networks

Meier, J. (author), Tewarie, P. (author), Van Mieghem, P. (author)

Communication between brain regions is still insufficiently understood. Applying concepts from network science has shown to be successful in gaining insight in the functioning of the brain. Recent work has implicated that especially shortest paths in the structural brain network seem to play a major role in the communication within the brain. So...

journal article 2015

document

Exact coupling threshold for structural transition reveals diversified behaviors in interconnected networks

Sahneh, F.D. (author), Scoglio, C. (author), Van Mieghem, P. (author)

An interconnected network features a structural transition between two regimes [F. Radicchi and A. Arenas, Nat. Phys. 9, 717 (2013)]: one where the network components are structurally distinguishable and one where the interconnected network functions as a whole. Our exact solution for the coupling threshold uncovers network topologies with...

journal article 2015

document

Survival time of the susceptible-infected-susceptible infection process on a graph

Van de Bovenkamp, R. (author), Van Mieghem, P. (author)

The survival time T is the longest time that a virus, a meme, or a failure can propagate in a network. Using the hitting time of the absorbing state in an uniformized embedded Markov chain of the continuous-time susceptible-infected-susceptible (SIS) Markov process, we derive an exact expression for the average survival time E[T ] of a virus in...

journal article 2015

document

An inequality of Gauss

Hooghiemstra, G. (author), Van Mieghem, P. (author)

In this article Gerard Hooghiemstra and Piet van Mieghem explain why the Gauss inequality is overshadowed by the Chebychev inequality. Furthermore, they present a proof of the Gauss inequality in modern notation.

journal article 2015

document

Hierarchical clustering in minimum spanning trees

Yu, M. (author), Hillebrand, A. (author), Tewarie, P. (author), Meier, J. (author), Van Dijk, B. (author), Van Mieghem, P. (author), Stam, C.J. (author)

The identification of clusters or communities in complex networks is a reappearing problem. The minimum spanning tree (MST), the tree connecting all nodes with minimum total weight, is regarded as an important transport backbone of the original weighted graph. We hypothesize that the clustering of the MST reveals insight in the hierarchical...

journal article 2015

document

Algebraic Connectivity of Interdependent Networks

Martin-Hernandez, J. (author), Wang, H. (author), Van Mieghem, P. (author), D'Agostino, G. (author)

The algebraic connectivity UN-1, i.e. the second smallest eigenvalue of the Laplacian matrix, plays a crucial role in dynamic phenomena such as diffusion processes, synchronization stability, and network robustness. In this work we study the algebraic connectivity in the general context of interdependent networks, or network-of-networks (NoN)....

journal article 2014

document

The Impact of the Topology on Cascading Failures in a Power Grid Model

Koç, Y. (author), Warnier, M. (author), Van Mieghem, P. (author), Kooij, R.E. (author), Brazier, F.M.T. (author)

Cascading failures are one of the main reasons for large scale blackouts in power transmission grids. Secure electrical power supply requires, together with careful operation, a robust design of the electrical power grid topology. Currently, the impact of the topology on grid robustness is mainly assessed by purely topological approaches, that...

journal article 2014

document

ILIGRA: An Efficient Inverse Line Graph Algorithm

Liu, D. (author), Trajanovski, S. (author), Van Mieghem, P. (author)

This paper presents a new and efficient algorithm, ILIGRA, for inverse line graph construction. Given a line graph H, ILIGRA constructs its root graph G with the time complexity being linear in the number of nodes in H. If ILIGRA does not know whether the given graph H is a line graph, it firstly assumes that H is a line graph and starts its...

journal article 2014

document

The Trees and the Forest: Characterization of complex brain networks with minimum spanning trees

Stam, C.J. (author), Tewarie, P. (author), Van Dellen, E. (author), Van Straaten, E.C.W. (author), Hillebrand, A. (author), Van Mieghem, P. (author)

In recent years there has been a shift in focus from the study of local, mostly task-related activation to the exploration of the organization and functioning of large-scale structural and functional complex brain networks. Progress in the interdisciplinary field of modern network science has introduced many new concepts, analytical tools and...

journal article 2014

document

Finding Critical Regions and Region-Disjoint Paths in a Network

Trajanovski, S. (author), Kuipers, F.A. (author), Ili?, A. (author), Crowcroft, J. (author), Van Mieghem, P. (author)

Due to their importance to society, communication networks should be built and operated to withstand failures.However, cost considerations make network providers less inclined to take robustness measures against failures that are unlikely to manifest, like several failures coinciding simultaneously in different geographic regions of their...

journal article 2014

document

Weighted Betweenness and Algebraic Connectivity

Martin-Hernandez, J. (author), Li, Z. (author), Van Mieghem, P. (author)

One of the better studied topology metrics of complex networks is the second smallest eigenvalue of the Laplacian matrix of a network’s graph, referred to as the algebraic connectivity mN-1. This spectral metric plays a decisive role in synchronization of coupled oscillators, network robustness, consensus problems, belief propagation, graph...

journal article 2014

document

Topology of molecular interaction networks

Winterbach, W. (author), Van Mieghem, P. (author), Reinders, M. (author), Wang, H. (author), De Ridder, D. (author)

Molecular interactions are often represented as network models which have become the common language of many areas of biology. Graphs serve as convenient mathematical representations of network models and have themselves become objects of study. Their topology has been intensively researched over the last decade after evidence was found that...

journal article 2013

document

Effect of the interconnected network structure on the epidemic threshold

Wang, H. (author), Li, Q. (author), D'Agostino, G. (author), Havlin, S. (author), Stanley, H.E. (author), Van Mieghem, P. (author)

Most real-world networks are not isolated. In order to function fully, they are interconnected with other networks, and this interconnection influences their dynamic processes. For example, when the spread of a disease involves two species, the dynamics of the spread within each species (the contact network) differs from that of the spread...

journal article 2013

document

Lognormal infection times of online information spread

Doerr, C. (author), Blenn, N. (author), Van Mieghem, P. (author)

The infection times of individuals in online information spread such as the inter-arrival time of Twitter messages or the propagation time of news stories on a social media site can be explained through a convolution of lognormally distributed observation and reaction times of the individual participants. Experimental measurements support the...

journal article 2013

document

Robustness Envelopes of Networks

Trajanovski, S. (author), Martín-Hernández, J. (author), Winterbach, W. (author), Van Mieghem, P. (author)

We study the robustness of networks under node removal, considering random node failure, as well as targeted node attacks based on network centrality measures. Whilst both of these have been studied in the literature, existing approaches tend to study random failure in terms of average-case behavior, giving no idea of how badly network...

journal article 2013

document

Generating graphs that approach a prescribed modularity

Trajanovski, S. (author), Kuipers, F.A. (author), Martín-Hernández, J. (author), Van Mieghem, P. (author)

Modularity is a quantitative measure for characterizing the existence of a community structure in a network. A network's modularity depends on the chosen partitioning of the network into communities, which makes finding the specific partition that leads to the maximum modularity a hard problem. In this paper, we prove that deciding whether a...

journal article 2013

document

Random line graphs and a linear law for assortativity

Liu, D. (author), Trajanovski, S. (author), Van Mieghem, P. (author)

For a fixed number N of nodes, the number of links L in the line graph H(N,L) can only appear in consecutive intervals, called a band of L. We prove that some consecutive integers can never represent the number of links L in H(N,L), and they are called a bandgap of L. We give the exact expressions of bands and bandgaps of L. We propose a model...

journal article 2013

document

Susceptible-infected-susceptible epidemics on the complete graph and the star graph: Exact analysis

Cator, E.A. (author), Van Mieghem, P. (author)

Since mean-field approximations for susceptible-infected-susceptible (SIS) epidemics do not always predict the correct scaling of the epidemic threshold of the SIS metastable regime, we propose two novel approaches: (a) an ?-SIS generalized model and (b) a modified SIS model that prevents the epidemic from dying out (i.e., without the...

journal article 2013

document

Maximum modular graphs

Trajanovski, S. (author), Wang, H. (author), Van Mieghem, P. (author)

Modularity has been explored as an important quantitative metric for community and cluster detection in networks. Finding the maximum modularity of a given graph has been proven to be NPcomplete and therefore, several heuristic algorithms have been proposed. We investigate the problem of finding the maximum modularity of classes of graphs that...

journal article 2012

document

Decreasing the spectral radius of a graph by link removals

Van Mieghem, P. (author), Stevanovi?, D. (author), Kuipers, F. (author), Li, C. (author), Van de Bovenkamp, R. (author), Liu, D. (author), Wang, H. (author)

The decrease of the spectral radius, an important characterizer of network dynamics, by removing links is investigated. The minimization of the spectral radius by removing m links is shown to be an NP-complete problem, which suggests considering heuristic strategies. Several greedy strategies are compared, and several bounds on the decrease of...

journal article 2011