Algebraic Connectivity of Interdependent Networks

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)....

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

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...

Nodal infection in Markovian susceptible-infected-susceptible and susceptible-infected-removed epidemics on networks are non-negatively correlated

By invoking the famous Fortuin, Kasteleyn, and Ginibre (FKG) inequality, we prove the conjecture that the correlation of infection at the same time between any pair of nodes in a network cannot be negative for (exact) Markovian susceptible-infected-susceptible (SIS) and susceptible-infected-removed (SIR) epidemics on networks. The truth of the...

Domination-time dynamics in susceptible-infected-susceptible virus competition on networks

When two viruses compete for healthy nodes in a simple network and both spreading rates are above the epidemic threshold, only one virus will survive. However, if we prevent the viruses from dying out, rich dynamics emerge. When both viruses are identical, one virus always dominates the other, but the dominating and dominated virus alternate. We...

ILIGRA: An Efficient Inverse Line Graph Algorithm

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...

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

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...

Finding Critical Regions and Region-Disjoint Paths in a Network

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...

Weighted Betweenness and Algebraic Connectivity

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...

Are Friends Overrated?: A Study for the Social Aggregator Digg.com

The key feature of online social networks is the ability of users to become active, make friends and interact with those around them. Such interaction is typically perceived as critical to these platforms; therefore, a significant share of research has investigated the characteristics of social links, friendship relations, community structure,...

Correlating the topology of a metabolic network with its growth capacity

Telecom and Energy, vital sectors enabling Smart Living

This thesis investigates the past, present and future of energy, telecom and household related developments aiming to pinpoint synergetic innovation possibilities. Providing overview and insights at the aggregation level above, being the sector network, is the first necessary step to reach this goal. The academic part of this thesis focuses on...

Emergence of modular structure in a large-scale brain network with interactions between dynamics and connectivity

A network of 32 or 64 connected neural masses, each representing a large population of interacting excitatory and inhibitory neurons and generating an electroencephalography/magnetoencephalography like output signal, was used to demonstrate how an interaction between dynamics and connectivity might explain the emergence of complex network...

Context-Aware Route Planning

In context-aware route planning, there is a set of transportation agents each with a start and destination location on a shared infrastructure. Each agent wants to find a shortest-time route plan without colliding with any of the other agents, or ending up in a deadlock situation. We present a single-agent route planning algorithm that is both...

Network protection against worms and cascading failures using modularity partitioning

Communication networks are prone to virus and worms spreading and cascading failures. Recently, a number of social networking worms have spread over public Web sites. Another example is error propagation in routing tables, such as in BGP tables. The immunization and error curing applied to these scenarios are not fast enough. There have been...

Graphs with given diameter maximizing the algebraic connectivity

We propose a class of graphs G?D(n1, n2, ..., nD+1), containing of a chain of D+1 cliques Kn1 , Kn2 , ..., KnD+1, where neighboring cliques are fully-interconnected. The class of graphs has diameter D and size N = ? 1?i?D+1ni. We prove that this class of graphs can achieve the maximal number of links, the minimum average hopcount, and more...

Fiedler’s Clustering on m?dimensional Lattice Graphs

We consider the partitioning of m-dimensional lattice graphs using Fiedler’s approach [1], that requires the determination of the eigenvector belonging to the second smallest eigenvalue of the Laplacian. We examine the general m-dimensional lattice and, in particular, the special cases: the 1-dimensional path graph PN and the 2-dimensional...

The value (driven) web

This paper presents a vision on the importance of values and ethical aspects in web science. We create(d) the Internet, but now the Internet (technology) is shaping our world increasingly: the way we experience, interact, transact, conduct business et cetera. The Internet is ubiquitous and vital to many aspects of our society; it is substituting...

Weight of a link in a shortest path tree and the Dedekind Eta function

The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding exact probability generating function and the asymptotic law are derived. As a remarkable coincidence, this asymptotic law is precisely the same as the distribution of the cost of one “job” in...