# Centrality-based identification of important edges in complex networks

Timo Bröhl<EMAIL_ADDRESS>Department of Epileptology, University of
Bonn Medical Centre, Sigmund-Freud-Straße 25, 53105 Bonn, Germany  Helmholtz
Institute for Radiation and Nuclear Physics, University of Bonn, Nussallee
14–16, 53115 Bonn, Germany  Klaus Lehnertz<EMAIL_ADDRESS>Department of Epileptology, University of Bonn Medical Centre, Sigmund-Freud-
Straße 25, 53105 Bonn, Germany  Helmholtz Institute for Radiation and Nuclear
Physics, University of Bonn, Nussallee 14–16, 53115 Bonn, Germany
Interdisciplinary Center for Complex Systems, University of Bonn, Brühler
Straße 7, 53175 Bonn, Germany

###### Abstract

Centrality is one of the most fundamental metrics in network science. Despite
an abundance of methods for measuring centrality of individual vertices, there
are by now only a few metrics to measure centrality of individual edges. We
modify various, widely used centrality concepts for vertices to those for
edges, in order to find which edges in a network are important between other
pairs of vertices. Focusing on the importance of edges, we propose an edge-
centrality-based network decomposition technique to identify a hierarchy of
sets of edges, where each set is associated with a different level of
importance. We evaluate the efficiency of our methods using various
paradigmatic network models and apply the novel concepts to identify important
edges and important sets of edges in a commonly used benchmark model in social
network analysis as well as in evolving epileptic brain networks.

> In a large number of natural and man-made networks, an edge represents some
> form of interaction between pairs of vertices. Examples include the climate,
> brain networks, protein-protein interactions, gene interactions, plant-
> pollinator interactions, food-webs, or communication and social networks, to
> name just a few. Improving understanding of structure and function of such
> interaction networks requires knowledge about their key constituents.
> Important vertices (or groups thereof) can be identified with a multitude of
> vertex centralities, however, there are only a few centrality-based concepts
> and metrics to identify important edges (or groups thereof). Here we propose
> straightforward modifications of widely used centrality concepts for
> vertices to those for edges and present a modification of the concept of
> network decomposition that allows one to identify sets of interconnected
> important edges. Using various paradigmatic network models and real data
> sets, we show how key network constituents – as identified with the same
> centrality concept – are related to each other and demonstrate how important
> edges highlight typical properties of network topologies.

##  I Introduction

The last decade witnessed an exceptional success of network theory and its
applications in diverse areas of science including physics, earth and climate
sciences, sociology, quantitative finance, biology, and the neurosciences
Boccaletti  _et al._ (2006); Arenas  _et al._ (2008); Bullmore and Sporns
(2009); Donges  _et al._ (2009); Allen and Elston (2011); Barthélemy (2011);
Barabási, Gulbahce, and Loscalzo (2011); Newman (2012); Baronchelli  _et al._
(2013); Lehnertz  _et al._ (2014); Heckmann, Schwanghart, and Phillips (2015);
Gao, Small, and Kurths (2016). A growing number of studies indicate that
research into the dynamics of spatially extended complex systems benefits from
a network approach, as it allows a refined exploration of relationships
between structure and dynamics in such systems. With this approach, a system
is described by an interaction network, whose vertices represent elementary
units of the system and whose edges represent interactions between them. There
is now increasing evidence that understanding of structure–dynamics
relationships can further be improved by allowing vertices and/or edges to
change with time, which leads to so-called evolving interaction networks Holme
and Saramäki (2012); Belykh  _et al._ (2014); Kivelä  _et al._ (2014);
Lehnertz  _et al._ (2014).

Previous studies mostly investigated macroscopic network properties (such as
clustering, efficiency, or assortativity) and reported non-trivial
characteristics for various empirically derived interaction networks. More
recently, special emphasis has been placed on the mesoscopic structural
organization (e.g., on communities Fortunato and Hric (2016), on motifs Alon
(2007); Fornito, Zalesky, and Breakspear (2015), or on core–periphery
structure Rombach  _et al._ (2014)) as well as on microscopic aspects, such as
the role of individual network constituents (i.e., vertices or edges) in
structure and dynamics of interaction networks Lü  _et al._ (2016). It is
clear that identifying key network constituents and characterizing their
importance for structure and dynamics of interaction networks is highly
relevant to improve understanding and controlling of the collective dynamics
Havlin  _et al._ (2014); Bialonski, Ansmann, and Kantz (2015); Liu and
Barabási (2016); Gates and Rocha (2016); Lehnertz  _et al._ (2016).

There are different concepts and a growing number of metrics – such as
centralities – that allow one to characterize the role of network vertices for
structure and dynamics Kuhnert  _et al._ (2012); Spitz and Horvát (2014);
Almgren and Lee (2016); Lü  _et al._ (2016); Geier and Lehnertz (2017a).
Interestingly, there are by now only a few metrics that characterize the role
of individual edges (e.g., metrics based on the so-called weak-ties hypothesis
Granovetter (1973), edge betweenness centrality Girvan and Newman (2002), or
bridgeness Cheng  _et al._ (2010)). This is quite remarkable, as one might
conjecture that an improved characterization of importance of edges in
interaction networks could add to advance understanding and control of such
networks Slotine and Liu (2012).

We here address this issue and propose modifications of various, widely used
centrality concepts for vertices to those for edges, in order to find which
edges in a network are important between other pairs of vertices. We
concentrate on eigenvector and closeness centrality, in addition to
betweenness centrality Girvan and Newman (2002).

Given the well known problem of ranking in networks Liao  _et al._ (2017), and
in order to provide a more global (mesoscopic) view of importance of sets of
edges and their role in structure and dynamics of interaction networks, we
modify the concept of network decomposition to identify a bottom-up hierarchy
of sets of edges, where each set is associated with a different level of
importance. We investigate characteristics of the proposed methods using
paradigmatic network models and apply the novel concepts to identify important
edges and important sets of edges in real-world networks.

##  II Estimating importance of vertices and edges

In the following, we consider undirected, binary or weighted networks that
consist of sets of vertices $\mathcal{V}$ and edges $\mathcal{E}$, with
$V=\left|\mathcal{V}\right|$ and $E=\left|\mathcal{E}\right|$ denoting the
number of vertices and edges, respectively.

The importance of network constituents can be assessed with the concept of
centrality that allows for various interpretations Lü  _et al._ (2016).
Centrality indices take into account the different roles network constituents
play in a network. Here, we concentrate on the concepts of betweenness,
closeness, and eigenvector centrality. Betweenness and closeness centrality
are based on shortest paths, which requires the definition of “length”
$d_{ij}$ of a path between vertices $i$ and $j$ or between edges $i$ and $j$.

The length $d_{ij}$ of a shortest path $P$ between vertices $i$ and $j$ in a
binary network is the number of edges along this path. We here utilize the
same definition for the length $d_{ij}$ of $P$ between edges $i$ and $j$. For
$i$ and $j$ being connected to a same vertex, we define
$d_{ij}\mathrel{\mathop{:}}=0$. In case of a weighted network, we relate the
length $d_{ij}$ of $P$ between vertices/edges $i$ and $j$ to the sum of the
inverse weights of edges along this path Freeman (1979). In case of adjacent
edges, i.e., edges connected by a single vertex, we again define
$d_{ij}\mathrel{\mathop{:}}=0$.

### Betweenness centrality

Following Refs. Newman (2001); Barrat  _et al._ (2004); Wang, Hernandez, and
Van Mieghem (2008); Opsahl, Agneessens, and Skvoretz (2010); Kuhnert  _et al._
(2012), vertex betweenness centrality (of vertex $k$) can be defined as

$\mathcal{C}^{\rm B}_{\rm v}(k)=\frac{2}{(V-1)(V-2)}\sum_{k\neq i\neq
j}\frac{q_{ij}(k)}{G_{ij}},$ (1)

where $\left\\{k,i,j\right\\}\in\mathcal{V}$, and $q_{ij}(k)$ is the number of
shortest paths between vertices $i$ and $j$ running through vertex $k$.
$G_{ij}$ is the total number of shortest paths between vertices $i$ and $j$.

Similarly, edge betweenness centrality (of edge $k$) can be defined as Freeman
(1977); Girvan and Newman (2002)

$\mathcal{C}^{\rm B}_{\rm e}(k)=\frac{2}{V(V-1)}\sum_{i\neq
j}\frac{q_{ij}(k)}{G_{ij}},$ (2)

where $k\in\mathcal{E}$, $\left\\{i,j\right\\}\in\mathcal{V}$, $q_{ij}(k)$ is
the number of shortest paths between vertices $i$ and $j$ running through edge
$k$, and $G_{ij}$ is the total number of shortest paths between vertices $i$
and $j$. A network constituent $k$ is the more important, the more commonly
this constituent is part of the shortest path between every possible pair of
vertices, excluding the pairs with vertex $k$.

### Closeness centrality

Vertex closeness centrality (for vertex $k$) is defined as

$\mathcal{C}^{\rm C}_{\rm v}(k)=\frac{V-1}{\sum_{l}d_{kl}}$ (3)

with $\left\\{k,l\right\\}\in\mathcal{V}$ and where $d_{kl}$ denotes the
length of the shortest path from vertex $k$ to vertex $l$.

Similarly, we define edge closeness centrality (for edge $k$) as

$\mathcal{C}^{\rm C}_{\rm e}(k)=\frac{E-1}{\sum_{l}d_{kl}},$ (4)

with $\left\\{k,l\right\\}\in\mathcal{E}$ and where $d_{kl}$ denotes the
length of the shortest path from edge $k$ to edge $l$. A network constituent
$k$ is the more important, the shorter the paths that connect this constituent
to every other reachable constituent of the same type.

### Eigenvector centrality

Vertex eigenvector centrality (of vertex $k$) is defined as the $k$th entry of
the eigenvector $\vec{v}$ corresponding to the dominant eigenvalue
$\lambda_{\max}$ of matrix ${\bf M}$, which we derive from the eigenvector
equation ${\bf M}\vec{v}=\lambda\vec{v}$ using the power iteration method:

$\mathcal{C}^{\rm E}_{\rm
v}(k)=\frac{1}{\lambda_{\max}}\sum_{l}M_{kl}\,\mathcal{C}^{\rm E}_{\rm v}(l),$
(5)

with $\left\\{k,l\right\\}\in\mathcal{V}$. Here ${\bf M}$ denotes the
adjacency matrix ${\bf A}^{\rm(v)}\in\left\\{0,1\right\\}^{V\times V}$ of a
binary network, with $A^{\rm(v)}_{ij}=1$ if there is an edge between vertices
$i$ and $j$, and 0 otherwise. In case of a weighted network, ${\bf M}$ denotes
the weight matrix ${\bf W}^{\rm(v)}\in\mathbb{R}_{+}^{V\times V}$, with
$W^{\rm(v)}_{ij}$ denoting the weight of an edge between vertices $i$ and $j$.
In a binary network, the degree $k_{i}$ of a vertex $i$ is defined as the
number of its neighbors ($k_{i}\mathrel{\mathop{:}}=\sum_{j}A^{\rm(v)}_{ij}$).
Its weighted counterpart is the strength
$s_{i}\mathrel{\mathop{:}}=\sum_{j}W^{\rm(v)}_{ij}$. We define
$A^{\rm(v)}_{ii}\mathrel{\mathop{:}}=0\,\forall\,i$ and
$W^{\rm(v)}_{ii}\mathrel{\mathop{:}}=0\,\forall\,i$ with
$i\in\left\\{1,\ldots,V\right\\}$.

Analogously, we define edge eigenvector centrality (of edge $k$):

$\mathcal{C}^{\rm E}_{\rm
e}(k)=\frac{1}{\lambda_{\max}}\sum_{l}M_{kl}\,\mathcal{C}^{\rm E}_{\rm e}(l),$
(6)

with $\left\\{k,l\right\\}\in\mathcal{E}$. Here ${\bf M}$ denotes the edge
adjacency matrix ${\bf A}^{\rm(e)}\in\left\\{0,1\right\\}^{E\times E}$ of a
binary network, with $A^{\rm(e)}_{ij}=1$ if edges $i$ and $j$ are connected to
a same vertex, and 0 otherwise. In case of a weighted network, ${\bf M}$
denotes the weight matrix ${\bf W}^{\rm(e)}\in\mathbb{R}_{+}^{E\times E}$
whose entries $W^{\rm(e)}_{ij}$ are assigned the average weight of edges $i$
and $j$ if these edges are connected to a same vertex, and 0 otherwise. As
above, we define $A^{\rm(e)}_{ii}\mathrel{\mathop{:}}=0\,\forall\,i$ and
$W^{\rm(e)}_{ii}\mathrel{\mathop{:}}=0\,\forall\,i$ with
$i\in\left\\{1,\ldots,E\right\\}$. A network constituent $k$ is important if
its adjacent constituents of the same type are also important.

With the aforementioned definitions, we regard a network constituent with the
highest centrality value as most important and the one with the lowest
centrality value as least important. In case of equal centrality values we
rank in order of appearance. This ranking allows us to compare findings
achieved with the various centrality concepts.

### Edge-centrality-based network decomposition

Network decomposition techniques such as the $k$-core/$k$-shell method Kitsak
_et al._ (2010) – together with recent generalizations to weighted networks
Garas, Schweitzer, and Havlin (2012); Eidsaa and Almaas (2013, 2016) –
partition a network into sub-structures that are directly linked to vertex
centrality. This allows to uncover tightly connected regions in a network such
as sets of vertices with high centrality connected to other such vertices. We
here modify this concept and propose an edge-centrality-based network
decomposition technique to identify a bottom-up hierarchy of sets of edges,
where each set is associated with a different level of importance. With an eye
to a spider web, we denote the resulting set(s) of edges as “web(s)”. Our
technique is related to the $k$-core/$s$-core network decomposition Eidsaa and
Almaas (2013, 2016) as well as to community detection algorithms Fortunato
(2010) and consists of the following steps to decompose a network with $E$
edges:

  1. 0.

initialize algorithm: set $E^{\prime}=E$ and set iteration $n=1$;

  2. 1.

estimate centrality $\mathcal{C}^{\bullet}_{\rm e}(m)$ for all edges
$m\in\left\\{1,\ldots,E^{\prime}\right\\}$ in the current network (where
$\bullet\in\left\\{\text{B,C,E}\right\\}$);

  3. 2.

choose the lowest centrality value as threshold value
$\Theta=\min_{m}\mathcal{C}^{\bullet}_{\rm e}(m)$, in order to eliminate less
central edges;

  4. 3.

every edge $m^{\prime}$ with $\mathcal{C}^{\bullet}_{\rm
e}(m^{\prime})\leq\Theta$ is assigned to the web of rank $n$ and is removed
from the current network (which decreases $E^{\prime}$); note that the $<$
sign holds for repetitions of step 3 within the $n$th iteration;

  5. 4.

repeat step 1 and step 3 until no further edge is assigned to the web of rank
$n$;

  6. 5.

continue with next iteration (increase $n$ by 1) at step 1, as long as there
are remaining edges to be assigned to webs;

  7. 6.

reverse ranking of webs; the most important web has rank 1.

We note that the edge-centrality-based network decomposition can lead to two
divisions of a network that are not helpful in identifying sets of edges
associated with different levels of importance. These cases are either an
assignment of all edges to only one web (number of webs $N_{W}=1$) or an
assignment of each edge to a web ($N_{W}=E$). We also note that edges in a web
do not have to be connected with each other.

We illustrate the algorithm by decomposing an example network (cf. Fig. 1a).
Starting with iteration $n=1$, $\mathcal{C}^{\rm B}_{\rm e}$-values is
initially calculated in step 1 (estimated values at each step of iteration $n$
are summarized in Table 1). In step 2, the lowest centrality value is chosen
as threshold ($\Theta=0.1$ marked red in Table 1). In step 3, every edge with
$\mathcal{C}^{\rm B}_{\rm e}$ $=\Theta$ is assigned to the web with rank $n=1$
and removed from the current network. Note that there is no edge with
$\mathcal{C}^{\rm B}_{\rm e}$ $<\Theta$, since step 3 is executed in this
iteration for the first time. In step 4, the algorithm loops back to step 1
and $\mathcal{C}^{\rm B}_{\rm e}$ of the remaining edges in the current
network are calculated. Step 2 is skipped and in step 3 no further edges are
assigned to the web of rank $n=1$, since the newly calculated
$\mathcal{C}^{\rm B}_{\rm e}$-values are larger than $\Theta$. Hence the
condition to exit the loop in step 4 is achieved, and the next iteration $n=2$
starts. In step 1, $\mathcal{C}^{\rm B}_{\rm e}$-values do not change, and in
step 2 the new threshold $\Theta=0.4$ is chosen for this iteration. In step 3,
all remaining edges but one are assigned to the web of rank $n=2$. In step 4,
we enter the loop in this iteration, going back to step 1, newly calculating
the centrality value of the remaining edge. As only this edge is left in the
network, one might expect $\mathcal{C}^{\rm B}_{\rm e}$ $=1$ for this edge.
However, the decomposition algorithm only removes edges from the network,
leaving the number of vertices unchanged (i.e. $V=5$ and not $V=2$ as one
might expect for a network consisting of one edge only), thus yielding
$\mathcal{C}^{\rm B}_{\rm e}$ $=0.1<0.4=\Theta$. Hence this remaining edge is
also assigned to the web of rank $n=2$. Lastly the ranking of webs is reversed
and the algorithm yields two webs (see lower part of Fig. 1).

Figure 1: $\mathcal{C}^{\rm B}_{\rm e}$-based network decomposition of an example network (a) consisting of $V=5$ vertices and $E=7$ edges (numbers on edges denote edge weights). The current networks after the first step 3 in iteration 1, after the first step 3 in iteration 2, and after the second step 3 in iteration 2 are shown in (b-d). The resulting webs are shown in the lower part of the figure. |  |  | edge
---|---|---|---
|  |  | (0,1) | (0,2) | (0,3) | (1,3) | (1,4) | (2,3) | (3,4)
n | step | ref. |  |  |  |  |  |  |
1 | 1 | a | 0.2 | 0.1 | 0.1 | 0.3 | 0.3 | 0.3 | 0.1
| 2 | a | 0.2 | 0.1 | 0.1 | 0.3 | 0.3 | 0.3 | 0.1
| 3 | b | 0.2 | - | - | 0.3 | 0.3 | 0.3 | -
| 1* | b | 0.4 | - | - | 0.6 | 0.4 | 0.4 | -
| 3* | b | 0.4 | - | - | 0.6 | 0.4 | 0.4 | -
2 | 1 | b | 0.4 | - | - | 0.6 | 0.4 | 0.4 | -
| 2 | b | 0.4 | - | - | 0.6 | 0.4 | 0.4 | -
| 3 | c | - | - | - | 0.6 | - | - | -
| 1* | c | - | - | - | 0.1 | - | - | -
| 3* | d | - | - | - | - | - | - | -
Table 1: Estimated $\mathcal{C}^{\rm B}_{\rm e}$-values at the respective
decomposition steps during iteration $n$ of the example network shown in Fig.
1. Repeating steps during iteration $n$ and resulting from step 4 are marked
with *. $\mathcal{C}^{\rm B}_{\rm e}$-values chosen as threshold $\Theta$ are
shown in red. Column ‘ref.’ refers to subplots (a-d) in Fig. 1.

##  III Characteristics of importance estimators

For our investigations, we consider paradigmatic network models, namely small-
world networks Watts and Strogatz (1998) (with rewiring probability $p=0.1$,
unless specified otherwise), scale-free networks Albert and Barabási (2002),
and random networks Erdős and Rényi (1959); Batagelj and Brandes (2005), for
each of which we generated 1000 realizations. For each realization of a
weighted network, weights were drawn from the uniform distribution
$\mathcal{U}(0,1)$. Other parameters for network generation were chosen such
that networks consisted of $E=200$ edges, on average (small-world networks:
four nearest neighbors; scale-free networks: each new vertex is attached to
two existing ones; random networks: probability for edge creation equals edge
density $\epsilon=2E(V(V-1)^{-1})$.

Here, we report our observations for weighted networks with $V=100$ vertices.
In general, findings obtained for binary networks are quite similar, and in
the following we report on differences only. We also obtained qualitatively
similar findings for larger network sizes ($V=200$, $E\simeq 400$) and thus
expect that our findings carry over to even larger network sizes. We note
though that computation times grows exponentially when increasing the number
of edges $E$.

Figure 2: Distributions of correlations between edge ranks and vertex ranks
for the investigated topologies of weighted networks and for the various
centrality concepts used to rate importance (top to bottom: $\mathcal{C}^{\rm
E}$, $\mathcal{C}^{\rm C}$, $\mathcal{C}^{\rm B}$). Data are shown separately
for the two vertices connected by an edge: blue colors refers to the vertex
with higher importance ($\text{v}_{>}$) and black colors to the less important
partner ($\text{v}_{<}$). The inset shows an exemplary scatterplot of vertex
ranks versus edge ranks for one realization of a small-world network.

###  III.1 Do important edges connect important vertices?

Due to the analogous definition of a given centrality for vertices and edges,
one might expect that important edges connect important vertices. For example,
with betweenness centrality as an estimate for importance, one might deduce
that if the flow of information through some edge is high, the flow through
the vertices connected by that edge is high as well, and an analogous
reasoning can be made for closeness centrality. With eigenvector centrality, a
vertex is the more important the more important its neighboring vertices are;
thus, an edge connecting two such vertices can also expected to be important.
It has to be taken into account, however, that more than one edge can be
linked to a single vertex and that in a connected network the number of edges
is generally higher than the number of vertices.

In order to answer the question whether important edges connect important
vertices, we rank – for a given centrality concept – importance of vertices
and edges by assigning the vertex/edge with the highest centrality value rank
1, the second-highest centrality value rank 2, etc. (in case of equal
centrality values we rank in order of appearance). In the following, we denote
with ($\text{v}_{>}$,$\text{v}_{<}$) a pair of vertices, connected by an edge,
with vertex $\text{v}_{>}$ having a higher importance than its partner
$\text{v}_{<}$. We perform correlation analyses of edge ranks and ranks of
vertices $\text{v}_{>}$ and of $\text{v}_{<}$.

Fig. 2 summarizes our findings for weighted networks. With eigenvector
centrality, we observe for all topologies high correlation values (Pearson’s
$r>0.8$ on average) between edge ranks and ranks of $\text{v}_{>}$ vertices
but with a higher abundance for scale-free and random networks. For these
topologies, correlations between edge ranks and ranks of $\text{v}_{<}$
vertices are less pronounced and less often, in contrast to small-world
networks for which distributions are quite similar. With closeness and
betweenness centrality, correlation values decrease in general (and even reach
mean values less than 0.5), nevertheless we observe with both centralities
higher correlations between edge ranks and ranks of $\text{v}_{<}$ vertices
than with ranks of $\text{v}_{>}$ vertices. These findings point to a linear
relationship between edge and vertex ranks in these binary and weighted
networks.

Given the high correlations between edge ranks and vertex ranks, we
investigate – for a given centrality concept – the frequency for an edge with
highest importance (maximum edge centrality) to link to a vertex with highest
importance (maximum vertex centrality). Furthermore we investigate the median
importance rank of the vertex connected via that edge to the vertex with
highest importance.

weighted | small-world | scale-free | random
---|---|---|---
network | $\cal{P}$ | ${R_{\rm m}}$ | $\cal{P}$ | ${R_{\rm m}}$ | $\cal{P}$ | ${R_{\rm m}}$
$\mathcal{C}^{\rm E}$ | 68 | 3 | 90 | 3 | 76 | 3
$\mathcal{C}^{\rm C}$ | 55 | 4 | 88 | 3 | 71 | 3
$\mathcal{C}^{\rm B}$ | 67 | 3 | 77 | 3 | 59 | 4
Table 2: Percentage ($\cal{P}$) of the weighted small-world, scale-free, and
random networks, for which an edge with highest importance (as identified with
maximum edge centrality ($\mathcal{C}^{\rm E}_{\rm e}$, $\mathcal{C}^{\rm
C}_{\rm e}$, or $\mathcal{C}^{\rm B}_{\rm e}$)) is connected to a vertex with
highest importance (as identified with maximum vertex centrality
($\mathcal{C}^{\rm E}_{\rm v}$, $\mathcal{C}^{\rm C}_{\rm v}$, or
$\mathcal{C}^{\rm B}_{\rm v}$)). The median rank of the opposing vertex is
denoted by ${R_{\rm m}}$.

Depending on the centrality concept (see Table 2), we observe such highest-
importance connections in about two-thirds of our realizations of small-world
and random networks and in an even higher percentage (up to 90 %) of scale-
free networks. The importance of the opposing vertex has rank 3, on average.
With these findings, we can conclude that important edges indeed connect
important vertices in a large majority of the investigated networks and that
the three centrality concepts rate importance of edges differently, as
expected.

###  III.2 Do important edges highlight typical properties of network
topologies?

Figure 3: Left: Fraction of shortest paths in weighted small-world networks
(rewiring probability $p=0.1$) that traverse an edge of a given rank. Edge
ranks estimated with eigenvector centrality (top), closeness centrality
(middle), and betweenness centrality (bottom). Means and standard deviations
(green lines and light-green shaded areas) from 1000 realizations of networks
with 200 edges each. Right: Dependence of fraction of shortest paths
traversing the most important edge on rewiring probability $p$. Lines are for
eye guidance only. Figure 4: Means and standard deviations of normalized
strength $\tilde{s}$ of $\text{v}_{>}$ vertices (blue) and $\text{v}_{<}$
vertices (black) connected by the five most important edges in 1000 weighted
scale-free networks. Edge importance estimated with eigenvector centrality
($\mathcal{C}^{\rm E}_{\rm e}$, circles), closeness centrality
($\mathcal{C}^{\rm C}_{\rm e}$, triangles), and betweenness centrality
($\mathcal{C}^{\rm B}_{\rm e}$, squares).

Addressing this question, we investigate in small-world networks a possible
relationship between edge centrality and shortest paths, and in scale-free
networks which vertices most important edges typically connect (e.g., core-
core, core-periphery, or periphery-periphery vertices).

For our small-world networks, we observe that edges with highest rank are, on
average, part of most shortest paths compared to edges with lower rank (cf.
Fig. 3). As long-range connections in small-world networks are also part of
most shortest paths by construction, this indicates that long-range
connections are the most important edges in these networks, if importance was
assessed with closeness or betweenness centrality, and to a lesser degree also
with eigenvector centrality.

For our weighted scale-free networks, we show in Fig. 4 the normalized
strength $\tilde{s}$
$\left(\tilde{s}=s(k)/\max_{v\in\mathcal{V}}s(v);k\in\left\\{\text{v}_{>},\text{v}_{<}\right\\}\right)$
of $\text{v}_{>}$ and $\text{v}_{<}$ vertices connected by the five most
important edges (rank 1 – 5). $\text{v}_{>}$ vertices that belong to the edge
with highest importance (maximum centrality value) have a high relative mean
strength ($\tilde{s}>0.8$) while that of the opposing $\text{v}_{<}$ vertex is
about 0.1 smaller. For eigenvector and closeness centrality, we observe
highest $\tilde{s}$ values for $\text{v}_{>}$ vertices belonging to edges with
importance ranks between 2 and 24, resp, 2 and 14. These findings indicate
that high-importance edges typically connect vertices within or close to the
core of a weighted scale-free network.

###  III.3 Can different edge centrality concepts identify the same most
important edge?

Figure 5: Percentage $\cal{P}$ of weighted small-world (left), scale-free
(middle), and random networks (right) with 1000 realizations each for which
different edge centralities ($\mathcal{C}^{\rm E}_{\rm e}$, $\mathcal{C}^{\rm
C}_{\rm e}$, $\mathcal{C}^{\rm B}_{\rm e}$) identify the same edge with a
given edge rank (top: $\mathcal{C}^{\rm E}_{\rm e}$ vs. $\mathcal{C}^{\rm
C}_{\rm e}$, middle: $\mathcal{C}^{\rm E}_{\rm e}$ vs. $\mathcal{C}^{\rm
B}_{\rm e}$, bottom: $\mathcal{C}^{\rm C}_{\rm e}$ vs. $\mathcal{C}^{\rm
B}_{\rm e}$).

Previous studies Bolland (1988); Stephenson and Zelen (1989); Nakao (1990);
Rothenberg  _et al._ (1995); Borgatti (2005); Newman (2005); Manimaran, Hegde,
and Mande (2009); Valente  _et al._ (2008); Nguyen  _et al._ (2011); Wang,
Winterbach, and van Mieghem (2011); Kuhnert  _et al._ (2012) reported on
correlations between various vertex centralities, which can lead to
identifying the same vertex as most important using different centrality
concepts. Although such a finding might underline the high importance of that
vertex, its interpretation is nonetheless hampered.

Following this line of research, we estimate the frequency of deriving the
same edge rank with different edge centrality concepts. Fig. 5 summarizes our
findings for all investigated weighted networks. We find with eigenvector and
closeness edge centrality the same most important edge in about 50 % of our
scale-free and random networks, and in about 20 % of our small-world networks.
Similarly, closeness and betweenness edge centrality identify the same most
important edge in 45 % of our scale-free networks. For other networks and
combinations of edge centrality concepts, we obtain concordant findings in
less than 30 % of cases and for most edges with a rank larger than or equal to
two, concordance only rarely exceeds chance level.

In case of binary networks, we find with eigenvector and closeness edge
centrality the same most important edge in about 63 %, 79 %, and 50 %
respectively in our small-world, scale-free, and random networks. For other
networks and combinations of edge centrality concepts, we obtain concordant
findings in less than 40 % of cases.

The high concordance levels seen for weighted scale-free and random networks
follow from the chosen weight distribution. With weights drawn from a uniform
distribution, there is a high probability for edges with highest weights to be
connected to high-strength (high-degree) vertices. Such a configuration is
predestined for an identification of the most important edge with eigenvector
and closeness edge centrality. We note that other weight distributions can
lead to different findings.

Figure 6:  Number of webs $N_{W}$ (means and standard deviations) derived with
the edge-centrality-based network decomposition technique using different edge
centralities ($\mathcal{C}^{\rm E}_{\rm e}$: green, $\mathcal{C}^{\rm C}_{\rm
e}$: yellow, $\mathcal{C}^{\rm B}_{\rm e}$: red). Data obtained from 1000
realizations of weighted (top) and binary (bottom) networks consisting of 200
edges.

###  III.4 Substructures in important webs

Given that edges in a web do not have to be connected with each other, we now
define a substructure to be connected and consist of at least two edges or to
be a solitary edge and investigate the substructure’s characteristics.

We begin by determining the number of webs $N_{W}$ that can be achieved with a
given edge centrality concept for the investigated weighted network
topologies, with $E=200$ edges each (see Fig. 6). This number, which is a
priori not known, allows us to rule out the above-mentioned cases of $N_{W}$
$=1$ (web containing one substructure consisting of all edges) or $N_{W}$ $=E$
(webs containing one substructure being a solitary edge). A decomposition
based on eigenvector or closeness edge centrality leads to about 100 webs for
weighted small-world and random networks and to about 140 webs for weighted
scale-free networks, on average. In contrast, if the decomposition was based
on betweenness edge centrality, we achieve about 25 webs, on average, for all
investigated weighted network topologies. Depending on initial conditions, we
observe highest spread for the eigenvector-edge-centrality-based
decomposition, followed by the closeness-edge-centrality-based decomposition,
and the smallest one for the betweenness-edge-centrality-based decomposition.
Apart from $N_{W}$ being reduced by a factor of about 2, we obtain comparable
results for binary networks, with the exception of the $\mathcal{C}^{\rm
B}_{\rm e}$-based decomposition, for which $N_{W}$ varies depending on
topology. These findings indicate that the number of achievable webs depends
on the network topology and to a greater extent on the edge centrality used
for the decomposition. We note that other weight distributions can lead to
different findings.

Figure 7: Occurrences of a certain number of substructures within the 10 most
important webs (color coded) in 1000 realizations of weighted small-world
(left), scale-free (middle), and random networks (right). Edge-centrality-
based network decompositions were performed with different edge centralities
(from top to bottom: $\mathcal{C}^{\rm E}_{\rm e}$, $\mathcal{C}^{\rm C}_{\rm
e}$, $\mathcal{C}^{\rm B}_{\rm e}$). Figure 8: Left: Number of edges merged
into the most important web $W_{1}$. Middle: Percentage overlap
$\Gamma_{\mathrm{web}}$ of edges in $W_{1}$ and $n_{\mathrm{e}}$ most
important edges, with $n_{\mathrm{e}}$ being the number of edges in $W_{1}$
(see left). Right: Percentage $\Gamma_{\mathrm{max}}$ of most important webs
$W_{1}$ containing the most important edge. Edge-centrality-based network
decompositions performed with different edge centralities ($\mathcal{C}^{\rm
E}_{\rm e}$: green, $\mathcal{C}^{\rm C}_{\rm e}$: yellow, $\mathcal{C}^{\rm
B}_{\rm e}$: red). Means and standard deviations obtained from 1000
realizations of weighted (top) and binary (bottom) small-world (SW), scale-
free (SF), and random (ER) networks, each consisting of 200 edges.

Having identified the number $N_{W}$ of webs, we next investigate the number
of substructures important webs are composed of. Fig. 7 summarizes our
findings for the ten most important webs in weighted networks. For each
topology, and independent of the employed edge centrality concept, we observe
the most important web $W_{1}$ (web with rank 1) to be composed of one
substructure. Depending on the employed edge centrality concept for the
decomposition, this single substructure consists of three edges in small-world
and of, on average, five edges in scale-free as well as of 115 edges in random
weighted networks (cf. Fig. 8, upper left; note that the zero variance of the
number of edges in $W_{1}$ seen with the $\mathcal{C}^{\rm E}_{\rm e}$-based
decomposition for all weighted network topologies is related to the concept
underlying this edge centrality). For our binary networks, we mostly obtain
comparable findings with the number of edges in the single substructure being
of the same order as seen with weighted networks (cf. Fig. 8, lower left). An
exception is the two- to eight-fold higher number of edges in $W_{1}$ of
scale-free and random binary networks achieved with the $\mathcal{C}^{\rm
E}_{\rm e}$\- and $\mathcal{C}^{\rm C}_{\rm e}$-based decompositions. This can
be related to the occurrence of recurrent, identical patterns (being higher in
scale-free than in random networks) which is well captured by these edge
centralities. The in general higher number of edges in $W_{1}$ as yielded by
the $\mathcal{C}^{\rm B}_{\rm e}$-based network decomposition can be related
to a discretization effect: this edge centrality only takes into account the
number of shortest paths and hence does not directly depend on the numerical
value of the respective path lengths.

We note that edges, which have been assigned to the most important
$\mathcal{C}^{\rm E}_{\rm e}$-based and $\mathcal{C}^{\rm C}_{\rm e}$-based
webs, connect vertices of which more than two-thirds have a degree of one
(data not shown). This indicates that substructures in these webs are star-
like, since the majority of their vertices are adjacent to only one of a few
high-degree vertices that represent the center of these star-like
substructures. This holds for the topologies investigated here.

As regards the most important $\mathcal{C}^{\rm B}_{\rm e}$-based web, the
number of vertices with degree one highly depends on the topology of the
network. For small-world, scale-free, and random networks we find about
$30\%$, $60\%$ and $40\%$, respectively, of vertices having degree one. Star-
like substructures can thus be observed preferentially in the most important
webs of scale-free networks.

Having investigated characteristics of substructures in most important webs,
we now address the question if these webs contain most important edges. In
Fig. 8 (middle) we report the percentage overlap $\Gamma_{\mathrm{web}}$ of
edges in most important webs, consisting of $n_{\mathrm{e}}$ edges, with the
$n_{\mathrm{e}}$ most important edges. Independent of topology but depending
on the employed centrality concept, we observe a rather small percentage
overlap ($\Gamma_{\mathrm{web}}<75\%$) for $\mathcal{C}^{\rm C}_{\rm e}$ and a
rather large one ($\Gamma_{\mathrm{web}}>90\%$) for $\mathcal{C}^{\rm B}_{\rm
e}$ in both weighted and binary networks. For $\mathcal{C}^{\rm B}_{\rm e}$,
this high overlap is to be expected, given the high number of edges in
$W_{1}$. For $\mathcal{C}^{\rm E}_{\rm e}$, $\Gamma_{\mathrm{web}}$ takes on
comparably high values of up to $100\%$ in binary networks, while we find
$\Gamma_{\mathrm{web}}<75\%$ in weighted networks. Interestingly, we obtain
similar results if we consider the most important edge only (Fig. 8 (right)).
These findings clearly indicate that the most important edge as assessed with
the different edge centralities is not necessarily contained in the most
important web.

We conclude that webs derived with our edge-centrality-based network
decomposition contain substructures of important edges, however not inevitably
containing the most important edge, in the networks analyzed here.

##  IV Application to real-world networks

Figure 9: Zachary’s karate club network. Numbered vertices represent the
members of the club and edges represent friendships, as determined by
observation of interactions. Edge weights are encoded as line thickness. The
two factions into which the club split during the course of the study are
indicated by circles (the club instructor’s group (vertex 1)) and squares (the
club administrator’s group (vertex 34)).

We now demonstrate the utility of our proposed methods for understanding which
edges or sets of edges in a real-world network are important, by testing them
on a commonly used benchmark model in social network analysis with known
hierarchical structure, namely the karate club at a US university in the 1970s
studied in detail by Zachary Zachary (1977), and on evolving functional brain
networks from an epilepsy patients transiting into and out of an epileptic
seizure Geier  _et al._ (2015).

###  IV.1 Zachary’s karate club network

The network consists of 34 persons (vertices) whose mutual friendship
relationships (78 edges) have been carefully investigated over a period of two
years. Due to contrasts between the club’s instructor (vertex 1) and the
administrator (vertex 34), the club finally split into two smaller groups (see
Fig. 9), which ultimately resulted in the instructor’s leaving and starting a
new club, taking about a half of the original club’s members with him.

We begin by investigating the importance of edges and vertices using the
various centrality concepts (see Sec. II) and report our findings in Tab. 3.
For the weighted karate club network, we find with vertex closeness centrality
vertex 34 (club administrator) as most important followed by vertex 1 (the
club’s instructor), and these vertices switch position in ranking when rating
their importance with vertex betweenness centrality. With vertex eigenvector
centrality, vertices 1 and 34 have rank 4 and 3, respectively. For the binary
karate club network, all vertex centralities identify either vertex 1 or
vertex 34 as most important. These findings confirm previous studies Everett
and Borgatti (1998); Batool and Niazi (2014); Qi  _et al._ (2015); Qiao, Shan,
and Zhou (2017).

Interestingly, with all employed edge centralities we find the most important
edge to connect pairs of vertices of which one partner is either vertex 1 or
vertex 34. Highest-ranked edges are identical for the binary and the weighted
karate club network. None of the edge centralities indexes a direct important
connection between vertices 1 and 34, as expected. We note though that edge
betweenness centrality points to a shortest path between these vertices via
vertex 32.

| weighted | rank
---|---|---
| network | 1 | 2 | 3 | 4
$\mathcal{C}^{\rm E}$ | vertex | 3 | 33 | 34 | 1
edge | {33,34} | {34,32} | {34,24} | {34,28}
$\mathcal{C}^{\rm C}$ | vertex | 34 | 1 | 20 | 22
edge | {1,3} | {34,33} | {2,3} | {9,3}
$\mathcal{C}^{\rm B}$ | vertex | 1 | 34 | 32 | 33
edge | {1,32} | {34,32} | {34,33} | {31,2}

| binary | rank
---|---|---
| network | 1 | 2 | 3 | 4
$\mathcal{C}^{\rm E}$ | vertex | 34 | 1 | 3 | 33
edge | {34,33} | {34,9} | {34,32} | {33,14}
$\mathcal{C}^{\rm C}$ | vertex | 1 | 3 | 34 | 32
edge | {1,3} | {1,32} | {34,32} | {3,32}
$\mathcal{C}^{\rm B}$ | vertex | 1 | 34 | 33 | 3
edge | {1,32} | {1,6} | {1,7} | {1,3}

Table 3: The top-4 ranked vertices and edges of the karate club network.
Importance estimated with eigenvector centrality ($\mathcal{C}^{\rm E}$),
closeness centrality ($\mathcal{C}^{\rm C}$), and betweenness centrality
($\mathcal{C}^{\rm B}$). For edges, we report the pair of vertices
($\text{v}_{>}$, $\text{v}_{<}$) connected by that edge. Figure 10: Most
important web (rank 1) obtained with an edge-centrality-based decomposition of
the weighted karate club network using edge eigenvector ($\mathcal{C}^{\rm
E}_{\rm e}$; top), edge closeness ($\mathcal{C}^{\rm C}_{\rm e}$; middle), and
edge betweenness centrality ($\mathcal{C}^{\rm B}_{\rm e}$; bottom). The
number of resulting webs amounted to $N_{W}=26$ using $\mathcal{C}^{\rm
E}_{\rm e}$, $N_{W}=43$ using $\mathcal{C}^{\rm C}_{\rm e}$, and $N_{W}=20$
using $\mathcal{C}^{\rm B}_{\rm e}$.

We proceed with our edge-centrality-based network decomposition and show in
Fig. 10 the most important webs in the weighted karate club network obtained
with eigenvector ($\mathcal{C}^{\rm E}_{\rm e}$), closeness ($\mathcal{C}^{\rm
C}_{\rm e}$), and betweenness edge centrality ($\mathcal{C}^{\rm B}_{\rm e}$).
With a decomposition based on $\mathcal{C}^{\rm E}_{\rm e}$ or on
$\mathcal{C}^{\rm C}_{\rm e}$, the most important web (rank 1) takes on a
star-like form with edges connecting the club administrator (vertex 34) to few
other members of his faction (except for vertex 9 in case of $\mathcal{C}^{\rm
C}_{\rm e}$). We observe a similar star-like web with edges connecting the
club instructor (vertex 1) to many other members of his faction at rank 11
only using the $\mathcal{C}^{\rm E}_{\rm e}$-based decomposition (data not
shown). No such web is observed with the $\mathcal{C}^{\rm C}_{\rm e}$-based
decomposition. The heterogeneous occurrences of star-like webs centered around
either vertex 34 or vertex 1 can be explained by the different connections of
these two vertices with the respective opposing fission group. While vertex 1
is connected to 15 out of 16 members of his faction and to one member of the
opposing faction, vertex 34 is connected to 14 out of 18 members of his
faction and to three members of the opposing faction. The in general higher
number of connections of vertex 34 explains the findings obtained with both
the $\mathcal{C}^{\rm E}_{\rm e}$\- and the $\mathcal{C}^{\rm C}_{\rm
e}$-based decomposition. Interestingly, the most important web obtained with
the $\mathcal{C}^{\rm B}_{\rm e}$-based decomposition essentially takes on two
star-like forms, both with edges connecting either the club instructor (vertex
1) or the club administrator (vertex 34) to almost all members of theirs
factions. We also find two paths in this web that connect vertices 1 and 34,
namely via vertices 3 and 32 as well as via 2 and 31, and both these edges lie
on shortest paths in the karate club network (cf. Fig. 9).

Figure 11: Same as Fig. 10 but for the binary karate club network. The number
of resulting webs amounted to $N_{W}=22$ using $\mathcal{C}^{\rm E}_{\rm e}$,
$N_{W}=22$ using $\mathcal{C}^{\rm C}_{\rm e}$, and $N_{W}=24$ using
$\mathcal{C}^{\rm B}_{\rm e}$.

If we consider the binary karate club network, the most important web obtained
with the $\mathcal{C}^{\rm B}_{\rm e}$-based decomposition resembles to a
large extent the one obtained for the weighted network. The most important
webs derived with the $\mathcal{C}^{\rm E}_{\rm e}$\- and $\mathcal{C}^{\rm
C}_{\rm e}$-based decompositions are identical and take on a star-like form
with edges connecting the club administrator (vertex 34) to almost all other
members of his faction and to a few members of the other faction. With lower-
rank webs ($\mathcal{C}^{\rm E}_{\rm e}$: rank 4; $\mathcal{C}^{\rm C}_{\rm
e}$: rank 2), we find a similar star-like form but centered at the club
instructor (vertex 1) with edges connecting to almost all members of this
faction and to only one member of the other faction (data not shown).

We note that mismatched or unmatched vertices in the different decompositions
are related to club members that had been identified by Zachary to only have a
weak affiliation with either of the two groups.

Overall, our edge centralities identified most important edges in the karate
club network that connect pairs of vertices of which one partner (either club
instructor or club administrator) is known to be most important a priori (and
confirmed to be most important with various vertex centralities). Our edge-
centrality-based network decomposition revealed sets of edges that connect the
two most important vertices (club instructor and club administrator) to their
respective factions. Depending on the used edge centrality concept, this
information is either contained in one web (typically the most important one)
or spreads across multiple webs.

###  IV.2 Evolving functional brain networks during an epileptic seizure

As a second example, we investigate evolving functional brain networks
Lehnertz  _et al._ (2014) that we derived from multichannel
electroencephalographic (EEG) data recorded from an epilepsy patient prior to,
during, and after a focal-onset seizure (see Fig. 12). Vertices of such
networks are usually associated with sensors that are placed to sufficiently
capture the dynamics of the sampled brain region, and edges represent time-
varying interactions between pairs of brain regions. The data were part of
previous studies Schindler  _et al._ (2007, 2008); Bialonski, Wendler, and
Lehnertz (2011); Geier  _et al._ (2015); Geier and Lehnertz (2017b); Stahn and
Lehnertz (2017) and were recorded from sensors (chronically implanted strip
and depth electrodes; see Fig. 12) placed on the cortex and within relevant
brain structures during the presurgical evaluation of the patient’s medically
uncontrollable epilepsy. Decisions regarding sensor placement were purely
clinically driven and were made independently of this study. EEG data from 44
sensors were sampled at 200 Hz, digitized using a 16-bit analog-to-digital
converter, filtered within a frequency range of 0.1–70 Hz, and referenced
against the average signal of two sensors outside the focal region. The
patient had signed informed consent that the clinical data might be used and
published for research purposes. The study protocol had been approved by the
ethics committee of the University of Bonn.

Figure 12:  (A) Schematics of sensors placed over the left and right temporal-
lateral and temporal-basal neocortex and of bilateral intrahippocampal
sensors. (B) Invasive electroencephalographic recording of a seizure from the
left (upper half) and right brain hemisphere (lower half). Block B1 indicates
the pre-seizure phase; blocks B2 and B3 indicate the first and second half of
the seizure (electroencephalographic seizure onset and ending determined
automatically Schindler  _et al._ (2007)); block B4 indicates the post-seizure
phase.

It is still matter of debate Zaveri  _et al._ (2009); Warren  _et al._ (2010);
Wilke, Worrell, and He (2011); Varotto  _et al._ (2012); Geier  _et al._
(2015); Zubler  _et al._ (2015); Goodfellow  _et al._ (2016); Khambhati  _et
al._ (2016); Li  _et al._ (2016) whether the region of the epileptic brain
from which first signs of seizure activity were recorded – the so called
seizure onset zone (SOZ) – is the most important network constituent.
Addressing this issue, many previous studies employed vertex centralities,
however, an investigation based on edge centralities has not yet been carried
out. Furthermore, characterization of edges and thus estimation of importance
are affected by a number of factors that can be related to the applied methods
of data acquisition and of analysis Geier and Lehnertz (2017b); Sanz-Garcia,
Rings, and Lehnertz (2018). These confounding factors can lead to ambiguities,
and we expect that our edge-centrality-based network decomposition can help to
avoid misinterpretations that result from ambiguities.

We here follow previous studies Schindler  _et al._ (2008); Bialonski,
Wendler, and Lehnertz (2011); Geier  _et al._ (2015); Geier and Lehnertz
(2017b); Stahn and Lehnertz (2017) and pursue a sliding-window approach which
allows for a time-resolved analysis of characteristics of evolving weighted
functional brain networks. To this end, we split the offline bandpass-filtered
(1–45 Hz) EEG time series into consecutive non-overlapping windows of 2.5 s
duration each (corresponding to $T=500$ data points) and normalize data from
each sensor (vertex) and each window to zero mean and unit variance. In order
to derive edges, we estimate the strength of interaction between any pair of
vertices $k$ and $l$ – regardless of their anatomical connectivity – using an
established data-driven method for studying time-variant changes in phase
synchronization in EEG time series. The mean phase coherence Mormann  _et al._
(2000) is defined as

$R_{kl}=\left|\frac{1}{T}\sum_{t=0}^{T}\exp{i\mkern
1.0mu}(\Phi_{k}(t)-\Phi_{l}(t))\right|,$ (7)

where $\Phi_{k}(t)$ are the instantaneous phases (here derived with the
Hilbert transform) of the EEG time series from vertex $k$. $R_{kl}$ is
confined to the interval $[0,1]$, and $R_{kl}=1$ indicates fully synchronized
systems. In the resulting weighted snapshot network, self-loops are excluded.

We begin by investigating the importance of edges and vertices in evolving
functional brain networks using closeness centrality (we note that we achieved
similar findings with other centralities). Since importance in such networks
can vary strongly over time Geier  _et al._ (2015); Geier and Lehnertz (2017b,
a), we partition the recording into four blocks of equal duration, with each
block containing the data from 13 consecutive snapshot networks, and report
aggregated values of importance characteristics. In the upper part of Fig. 13,
we present the most important vertices and edges together with their temporal
stability during each block’s duration. We observe that most important
vertices, and particularly those with a comparably high temporal stability,
indicate brain regions outside the SOZ and even from the opposite brain
hemisphere to be most relevant for seizure dynamics Geier  _et al._ (2015).

Figure 13: Top: Most important edges and vertices (top) and most important web
(rank 1, bottom) projected onto a schematics of implanted sensors shown in
Fig. 12. The web was derived with the $\mathcal{C}^{\rm C}_{\rm e}$-based
decomposition of the snapshot networks. Color (vertices and edges) and line
thickness (edges) encode the relative amount of time $\Delta$ during each
block for which a vertex/edge is rated as most important. Sensors (vertices)
marked with ‘x’ record from the clinically defined seizure onset zone.

In contrast, most important and temporally most stable edges do not connect
most important vertices and point to interactions close to and within the SOZ
as most relevant for seizure dynamics. Interestingly, they also point to
homologous regions in the opposite brain hemisphere to be involved in the
spreading of seizure activity.

In the lower part of Fig. 13, we present our findings obtained from applying
our edge-centrality-based network decomposition, which leads to $N_{W}$ =650
webs, on average, with about 10 edges merged into the most important web
$W_{1}$ (web with rank 1). The vast majority of temporally most stable edges
point to interactions close to and within the SOZ as most relevant for seizure
dynamics during most pre-seizure, seizure, and post-seizure phase.

Although these findings need to be validated on a larger database, they
indicate that characterizing important edges or groups thereof in evolving
functional brain networks can help to improve understanding of the complicated
spatial-temporal dynamics of the epileptic process.

##  V Conclusions

We modified various, widely used centrality concepts for vertices to those for
edges, in order to find which edges in a network are important between other
pairs of vertices. We also proposed an edge-centrality-based network
decomposition technique to identify a bottom-up hierarchy of sets of edges or
webs, where each web is associated with a different level of importance. We
investigated characteristics of the proposed edge centralities using
paradigmatic binary and weighted network models. We could demonstrate that
despite the close relationship between importance of edges and vertices, edge
centralities provide additional information about the network constituents for
various topologies.

With the aim to identify important edges and important webs, we applied the
novel concepts to a widely used benchmark model in social network analysis as
well as to evolving epileptic brain networks. Our edge-centrality-based
network decomposition allowed us to identify a hierarchy of webs associated
with levels of importance, which we consider advantageous particularly for
those situations in which the most important edge can not be identified
unambiguously Liao  _et al._ (2017). Our decomposition technique might also be
of interest for identifying communities in networks Fortunato and Hric (2016).
If these communities are considered a grouping of vertices, these vertices are
allowed to be associated with multiple communities. Our decomposition might
also allow an alternative definition of communities, considering them as a
grouping of edges.

In the majority of cases our decomposition technique identified a star-like
structure as the most important web. Given that such structures are considered
relevant for synchronization and percolation phenomena on complex networks
Boccaletti  _et al._ (2016), our edge-centrality-based network decomposition
technique could help gaining deeper insights into such phenomena in real-world
networks.

Eventually, and with an eye on the inference of networks from multivariate
time series, we are confident that the concepts and methods proposed here can
help to improve characterization of networks through a data-driven
identification of important edges or important webs.

## Acknowledgements

The authors would like to thank Thorsten Rings, Kirsten Simon, Sarmed Hussain,
and Michael Roskosch for interesting discussions and for critical comments on
earlier versions of the manuscript. This work was supported by the Deutsche
Forschungsgemeinschaft (Grant No: LE 660/7-1).

## References

  * Boccaletti  _et al._ (2006) S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, “Complex networks: Structure and dynamics,” Phys. Rep. 424, 175–308 (2006).
  * Arenas  _et al._ (2008) A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, and C. Zhou, “Synchronization in complex networks,” Phys. Rep. 469, 93–153 (2008).
  * Bullmore and Sporns (2009) E. Bullmore and O. Sporns, “Complex brain networks: graph theoretical analysis of structural and functional systems,” Nat. Rev. Neurosci. 10, 186–198 (2009).
  * Donges  _et al._ (2009) J. F. Donges, Y. Zou, N. Marwan, and J. Kurths, “The backbone of the climate network,” Europhys. Lett. 87, 48007 (2009).
  * Allen and Elston (2011) R. J. Allen and T. C. Elston, “From physics to pharmacology?” Rep. Prog. Phys. 74, 016601 (2011).
  * Barthélemy (2011) M. Barthélemy, “Spatial networks,” Phys. Rep. 499, 1–101 (2011).
  * Barabási, Gulbahce, and Loscalzo (2011) A.-L. Barabási, N. Gulbahce, and J. Loscalzo, “Network medicine: a network-based approach to human disease,” Nat. Rev. Genet. 12, 56–68 (2011).
  * Newman (2012) M. E. J. Newman, “Communities, modules and large-scale structure in networks,” Nat. Phys. 8, 25–31 (2012).
  * Baronchelli  _et al._ (2013) A. Baronchelli, R. F. i Cancho, R. Pastor-Satorras, N. Chater, and M. H. Christiansen, “Networks in cognitive science,” Trends Cogn. Sci. 17, 348–360 (2013).
  * Lehnertz  _et al._ (2014) K. Lehnertz, G. Ansmann, S. Bialonski, H. Dickten, C. Geier, and S. Porz, “Evolving networks in the human epileptic brain,” Physica D 267, 7–15 (2014).
  * Heckmann, Schwanghart, and Phillips (2015) T. Heckmann, W. Schwanghart, and J. D. Phillips, “Graph theory – recent developments of its application in geomorphology,” Geomorphology 243, 130–146 (2015).
  * Gao, Small, and Kurths (2016) Z.-K. Gao, M. Small, and J. Kurths, “Complex network analysis of time series,” EPL (Europhysics Letters) 116, 50001 (2016).
  * Holme and Saramäki (2012) P. Holme and J. Saramäki, “Temporal networks,” Phys. Rep. 519, 97–125 (2012).
  * Belykh  _et al._ (2014) I. Belykh, M. di Bernardo, J. Kurths, and M. Porfiri, “Evolving dynamical networks,” Physica D 267, 1 – 6 (2014).
  * Kivelä  _et al._ (2014) M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, “Multilayer networks,” J. Complex Netw. 2, 203–271 (2014).
  * Fortunato and Hric (2016) S. Fortunato and D. Hric, “Community detection in networks: A user guide,” Phys. Rep. 659, 1 – 44 (2016).
  * Alon (2007) U. Alon, “Network motifs: theory and experimental approaches,” Nat. Rev. Gen. 8, 450–461 (2007).
  * Fornito, Zalesky, and Breakspear (2015) A. Fornito, A. Zalesky, and M. Breakspear, “The connectomics of brain disorders,” Nat. Rev. Neurosci. 16, 159–172 (2015).
  * Rombach  _et al._ (2014) M. P. Rombach, M. A. Porter, J. H. Fowler, and P. J. Mucha, “Core-periphery structure in networks,” SIAM J. Appl. Math. 74, 167–190 (2014).
  * Lü  _et al._ (2016) L. Lü, D. Chen, X.-L. Ren, Q.-M. Zhang, Y.-C. Zhang, and T. Zho, “Vital nodes identification in complex networks,” Phys. Rep. 650, 1–63 (2016).
  * Havlin  _et al._ (2014) S. Havlin, D. Y. Kenett, A. Bashan, J. Gao, and H. E. Stanley, “Vulnerability of network of networks,” Eur. Phys. J. ST 223, 2087–2106 (2014).
  * Bialonski, Ansmann, and Kantz (2015) S. Bialonski, G. Ansmann, and H. Kantz, “Data-driven prediction and prevention of extreme events in a spatially extended excitable system,” Phys. Rev. E 92, 042910 (2015).
  * Liu and Barabási (2016) Y.-Y. Liu and A.-L. Barabási, “Control principles of complex systems,” Rev. Mod. Phys. 88, 035006 (2016).
  * Gates and Rocha (2016) A. J. Gates and L. M. Rocha, “Control of complex networks requires both structure and dynamics,” Sci. Rep. 6, 24456 (2016).
  * Lehnertz  _et al._ (2016) K. Lehnertz, H. Dickten, S. Porz, C. Helmstaedter, and C. E. Elger, “Predictability of uncontrollable multifocal seizures – towards new treatment options,” Sci. Rep. 6, 24584 (2016).
  * Kuhnert  _et al._ (2012) M.-T. Kuhnert, C. Geier, C. E. Elger, and K. Lehnertz, “Identifying important nodes in weighted functional brain networks: A comparison of different centrality approaches,” Chaos 22, 023142 (2012).
  * Spitz and Horvát (2014) A. Spitz and E.-A. Horvát, “Measuring long-term impact based on network centrality: Unraveling cinematic citations,” PLoS ONE 9, e108857 (2014).
  * Almgren and Lee (2016) K. Almgren and J. Lee, “An empirical comparison of influence measurements for social network analysis,” Soc. Netw. Anal. Min. 6, 52 (2016).
  * Geier and Lehnertz (2017a) C. Geier and K. Lehnertz, “Long-term variability of importance of brain regions in evolving epileptic brain networks,” Chaos 27, 043112 (2017a).
  * Granovetter (1973) M. S. Granovetter, “The strength of weak ties,” Am. J. Sociol. 78, 1360–1380 (1973).
  * Girvan and Newman (2002) M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci. U.S.A. 99, 7821–7826 (2002).
  * Cheng  _et al._ (2010) X.-Q. Cheng, F.-X. Ren, H.-W. Shen, Z.-K. Zhang, and T. Zhou, “Bridgeness: a local index on edge significance in maintaining global connectivity,” J. Stat. Mech. Theor. Exp. 2010, P10011 (2010).
  * Slotine and Liu (2012) J.-J. Slotine and Y.-Y. Liu, “Complex networks: the missing link,” Nat. Phys. 8, 512–513 (2012).
  * Liao  _et al._ (2017) H. Liao, M. S. Mariani, M. Medo, Y.-C. Zhang, and M.-Y. Zhou, “Ranking in evolving complex networks,” Phys. Rep. 689, 1–54 (2017).
  * Freeman (1979) L. C. Freeman, “Centrality in social networks: Conceptual clarification,” Soc. Networks 1, 215–239 (1979).
  * Newman (2001) M. E. J. Newman, “Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality,” Phys. Rev. E 64, 016132 (2001).
  * Barrat  _et al._ (2004) A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani, “The architecture of complex weighted networks,” Proc. Natl. Acad. Sci. U.S.A. 101, 3747–3752 (2004).
  * Wang, Hernandez, and Van Mieghem (2008) H. Wang, J. M. Hernandez, and P. Van Mieghem, “Betweenness centrality in a weighted network,” Phys. Rev. E 77, 046105 (2008).
  * Opsahl, Agneessens, and Skvoretz (2010) T. Opsahl, F. Agneessens, and J. Skvoretz, “Node centrality in weighted networks: Generalizing degree and shortest paths,” Soc. Networks 32, 245–251 (2010).
  * Freeman (1977) L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry 40, 35–41 (1977).
  * Kitsak  _et al._ (2010) M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, “Identification of influential spreaders in complex networks,” Nat. Phys. 6, 888–893 (2010).
  * Garas, Schweitzer, and Havlin (2012) A. Garas, F. Schweitzer, and S. Havlin, “A $k$-shell decomposition method for weighted networks,” New J. Phys. 14, 083030 (2012).
  * Eidsaa and Almaas (2013) M. Eidsaa and E. Almaas, “$s$-core network decomposition: A generalization of $k$-core analysis to weighted networks,” Phys. Rev. E 88, 062819 (2013).
  * Eidsaa and Almaas (2016) M. Eidsaa and E. Almaas, “Investigating the relationship between k-core and s-core network decompositions,” Physica A 449, 111–125 (2016).
  * Fortunato (2010) S. Fortunato, “Community detection in graphs,” Phys. Rep. 486, 75–174 (2010).
  * Watts and Strogatz (1998) D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature 393, 440–442 (1998).
  * Albert and Barabási (2002) R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Rev. Mod. Phys. 74, 47–97 (2002).
  * Erdős and Rényi (1959) P. Erdős and A. Rényi, “On random graphs I,” Publ. Math. Debrecen 6, 290–297 (1959).
  * Batagelj and Brandes (2005) V. Batagelj and U. Brandes, “Efficient generation of large random networks,” Phys. Rev. E 71, 036113 (2005).
  * Bolland (1988) J. M. Bolland, “Sorting out centrality: An analysis of the performance of four centrality models in real and simulated networks,” Soc. Networks 10, 233–253 (1988).
  * Stephenson and Zelen (1989) K. Stephenson and M. Zelen, “Rethinking centrality: Methods and examples,” Soc. Networks 11, 1 – 37 (1989).
  * Nakao (1990) K. Nakao, “Distribution of measures of centrality: enumerated distributions of Freeman’s graph centrality measures.” Connections 13, 10–22 (1990).
  * Rothenberg  _et al._ (1995) R. B. Rothenberg, J. J. Potterat, D. E. Woodhouse, W. W. Darrow, S. Q. Muth, and A. S. Klovdahl, “Choosing a centrality measure: Epidemiologic correlates in the Colorado Springs study of social networks,” Soc. Networks 17, 273 – 297 (1995).
  * Borgatti (2005) S. P. Borgatti, “Centrality and network flow,” Soc. Networks 27, 55–71 (2005).
  * Newman (2005) M. E. J. Newman, “A measure of betweenness centrality based on random walks,” Soc. Networks 27, 39–54 (2005).
  * Manimaran, Hegde, and Mande (2009) P. Manimaran, S. R. Hegde, and S. C. Mande, “Prediction of conditional gene essentiality through graph theoretical analysis of genome-wide functional linkages,” Mol. BioSyst. 5, 1936–1942 (2009).
  * Valente  _et al._ (2008) T. W. Valente, K. Coronges, C. Lakon, and E. Costenbader, “How correlated are network centrality measures?” Connections 28, 16–26 (2008).
  * Nguyen  _et al._ (2011) T.-P. Nguyen, M. Scotti, M. J. Morine, and C. Priam, “Model-based clustering reveals vitamin D dependent multi-centrality hubs in a network of vitamin-related proteins,” BMC Syst. Biol. 5, 195 (2011).
  * Wang, Winterbach, and van Mieghem (2011) H. Wang, W. Winterbach, and P. van Mieghem, “Assortativity of complementary graphs,” Eur. Phys. J. B 83, 203–214 (2011).
  * Zachary (1977) W. W. Zachary, “An information flow model for conflict and fission in small groups,” J. Anthropol. Res. 33, 452–473 (1977).
  * Geier  _et al._ (2015) C. Geier, S. Bialonski, C. E. Elger, and K. Lehnertz, “How important is the seizure onset zone for seizure dynamics?” Seizure 25, 160–166 (2015).
  * Everett and Borgatti (1998) M. G. Everett and S. P. Borgatti, “Analyzing clique overlap,” Connections 21, 49–61 (1998).
  * Batool and Niazi (2014) K. Batool and M. A. Niazi, “Towards a methodology for validation of centrality measures in complex networks,” PLoS ONE 9, e90283 (2014).
  * Qi  _et al._ (2015) X. Qi, E. Fuller, R. Luo, and C.-Q. Zhang, “A novel centrality method for weighted networks based on the Kirchhoff polynomial,” Pattern Recognit. Lett. 58, 51–60 (2015).
  * Qiao, Shan, and Zhou (2017) T. Qiao, W. Shan, and C. Zhou, “How to identify the most powerful node in complex networks? A novel entropy centrality approach,” Entropy 19, 614 (2017).
  * Schindler  _et al._ (2007) K. Schindler, H. Leung, C. E. Elger, and K. Lehnertz, “Assessing seizure dynamics by analysing the correlation structure of multichannel intracranial EEG,” Brain 130, 65–77 (2007).
  * Schindler  _et al._ (2008) K. Schindler, S. Bialonski, M.-T. Horstmann, C. E. Elger, and K. Lehnertz, “Evolving functional network properties and synchronizability during human epileptic seizures,” Chaos 18, 033119 (2008).
  * Bialonski, Wendler, and Lehnertz (2011) S. Bialonski, M. Wendler, and K. Lehnertz, “Unraveling spurious properties of interaction networks with tailored random networks,” PLoS ONE 6, e22826 (2011).
  * Geier and Lehnertz (2017b) C. Geier and K. Lehnertz, “Which brain regions are important for seizure dynamics in epileptic networks? Influence of link identification and EEG recording montage on node centralities,” Int. J. Neural Syst. 27, 1650033 (2017b).
  * Stahn and Lehnertz (2017) K. Stahn and K. Lehnertz, “Surrogate-assisted identification of influences of network construction on evolving weighted functional networks,” Chaos 27, 123106 (2017).
  * Zaveri  _et al._ (2009) H. P. Zaveri, S. M. Pincus, I. I. Goncharova, R. B. Duckrow, D. D. Spencer, and S. S. Spencer, “Localization-related epilepsy exhibits significant connectivity away from the seizure-onset area,” NeuroReport 20, 891–895 (2009).
  * Warren  _et al._ (2010) C. Warren, S. Hu, M. Stead, B. H. Brinkmann, M. R. Bower, and G. A. Worrell, “Synchrony in normal and focal epileptic brain: The seizure onset zone is functionally disconnected,” J. Neurophysiol. 104, 3530–3539 (2010).
  * Wilke, Worrell, and He (2011) C. Wilke, G. Worrell, and B. He, “Graph analysis of epileptogenic networks in human partial epilepsy,” Epilepsia 52, 84–93 (2011).
  * Varotto  _et al._ (2012) G. Varotto, L. Tassi, S. Franceschetti, R. Spreafico, and F. Panzica, “Epileptogenic networks of type II focal cortical dysplasia: A stereo-EEG study,” NeuroImage 61, 591–598 (2012).
  * Zubler  _et al._ (2015) F. Zubler, H. Gast, E. Abela, C. Rummel, M. Hauf, R. Wiest, C. Pollo, and K. Schindler, “Detecting functional hubs of ictogenic networks,” Brain Topogr. 28, 305–317 (2015).
  * Goodfellow  _et al._ (2016) M. Goodfellow, C. Rummel, E. Abela, M. P. Richardson, K. Schindler, and J. R. Terry, “Estimation of brain network ictogenicity predicts outcome from epilepsy surgery,” Sci. Rep. 6, 29215 (2016).
  * Khambhati  _et al._ (2016) A. N. Khambhati, K. A. Davis, T. H. Lucas, B. Litt, and D. S. Bassett, “Virtual cortical resection reveals push-pull network control preceding seizure evolution,” Neuron 91, 1170–1182 (2016).
  * Li  _et al._ (2016) Y.-H. Li, X.-L. Ye, Q.-Q. Liu, J.-W. Mao, P.-J. Liang, J.-W. Xu, and P.-M. Zhang, “Localization of epileptogenic zone based on graph analysis of stereo-EEG,” Epilepsy Res. 128, 149–157 (2016).
  * Sanz-Garcia, Rings, and Lehnertz (2018) A. Sanz-Garcia, T. Rings, and K. Lehnertz, “Impact of type of intracranial EEG sensors on link strengths of evolving functional brain networks,” Physiol. Meas. 39, 074003 (2018).
  * Mormann  _et al._ (2000) F. Mormann, K. Lehnertz, P. David, and C. E. Elger, “Mean phase coherence as a measure for phase synchronization and its application to the EEG of epilepsy patients,” Physica D 144, 358–369 (2000).
  * Boccaletti  _et al._ (2016) S. Boccaletti, J. Almendral, S. Guan, I. Leyva, Z. Liu, I. Sendiña-Nadal, Z. Wang, and Y. Zou, “Explosive transitions in complex networks’ structure and dynamics: Percolation and synchronization,” Phys. Rep. 660, 1–94 (2016).


# On Nash-solvability of finite $n$-person deterministic graphical games;
Catch 22

Vladimir Gurvich  HSE University, Moscow Russia; e-mail<EMAIL_ADDRESS>;
<EMAIL_ADDRESS>
###### Abstract

We consider finite $n$-person deterministic graphical (DG) games. These games
are modelled by finite directed graphs (digraphs) $G$ which may have directed
cycles and, hence, infinite plays. Yet, it is assumed that all these plays are
equivalent and form a single outcome $c$, while the terminal vertices
$V_{T}=\\{a_{1},\ldots,a_{p}\\}$ form $p$ remaining outcomes.
We study the existence of Nash equilibria (NE) in pure stationary strategies.
It is known that NE exist when $n=2$ and may fail to exist when $n>2$. Yet,
the question becomes open for $n>2$ under the following extra condition:
(C) For each of $n$ players $c$ is worse than each of $p$ terminal outcomes.
In other words, all players are interested in terminating the play, which is a
natural assumption. Moreover, Nash-solvability remains open even if we replace
(C) by a weaker condition:
(C22) There exist no two players for whom $c$ is better than (at least) two
terminal outcomes.
We conjecture that such two players exist in each NE-free DG game, or in other
words, that (C22) implies Nash-solvability, for all $n$.
Recently, the DG games were extended to a wider class of the DG multi-stage
(DGMS) games, whose outcomes are the strongly connected components (SCC) of
digraph $G$. Merging all outcomes of a DGMS game that correspond to its non-
terminal SCCs we obtain a DG game. Clearly, this operation respects Nash-
solvability (NS). Basic conditions and conjectures related to NS can be
extended from the DG to DGMS games: in both cases NE exist if $n=2$ and may
fail to exist when $n>2$; furthermore,, we modify conditions (C) and (C22) to
adapt them for the DGMS games.
Keywords: $n$-person deterministic graphical (multi-stage) games, Nash
equilibrium, Nash-solvability, pure stationary strategy, digraph, directed
cycle, strongly connected component.

##  1 Deterministic graphical finite $n$-person games

Nash-solvability (NS) of these games is discussed in [2]. Here we use the
concepts, definitions, and notation from this paper.

NS holds for $n=2$ and may fail for $n>2$; see respectively Sections 5 and 2
of [2]. The first NE-free example was constructed for $n=4$ in the preprint
[7] and published in [3] 111Vladimir Oudalov refused to co-author paper [3]
published in Russia. Then, a much more compact example for $n=3$ appeared in
[2, Section 3]. In this example $c$ is the worst outcome for player 2 but for
players 1 and 3 $c$ is better than (at least) two terminal outcomes. Somewhat
surprisingly, computations show that such two players exist in each NE-free
$n$-person DG game (for all $n>2$). In other words, condition (C22) given in
Abstract implies NS. We call this conjecture ”Catch 22”. It is stronger than
conjecture ”(C) implies NS”, since condition (C22) is weaker than (C).

The latter means that every player strictly prefers each terminal play to each
infinite one, which looks natural and can be easily interpreted [5, Section
3.2] for examples. If (C) does not imply NS then there exists a DG game that
has a cyclic NE (with outcome $c$) but has no terminal NE (with an outcome
$a\in V_{T}$) although $V_{T}$ can be reached from the initial position [2,
Proposition 3]. This property looks strange but not impossible.

To formulate (C22) more accurately denote by $k_{c}(i)$ the number of
terminals that are worse than $c$ for player $i\in I=\\{1,\ldots,n\\}$. Then,
(C22) does not hold if and only if $k_{c}(i)\geq 2$ for (at least) two
players.

Digraph $G$ is called bidirected if each non-terminal move in it is
reversible, that is, $v^{\prime}v^{\prime\prime}\in E(G)$ if and only if
$v^{\prime\prime}v^{\prime}\in E(G)$ unless $v^{\prime}$ or $v^{\prime\prime}$
is a terminal position. We conjecture that every $n$-person DG game on a
finite bidirected digraph is NS.

##  2 Deterministic graphical multi-stage (DGMS) finite $n$-person games

Recently, DG games were generalized and DGMS games were introduced in [4,
Section 1]; see also [6, Section 4.1]. Here we use to the concepts,
definitions, and notation from these papers.

It is well-known that every digraph $G$ is uniquely partitioned into the
strongly connected components (SCC). An SCC will be called;

  * terminal if it has no outgoing edges (exits);

  * interior if it is not terminal and contains a directed cycle;

  * transient if it is neither terminal not interior.

Obviously, each transient component consists of a single non-terminal vertex.
Contracting every SCC to a single vertex, one gets an acyclic digraph.
Conversely, given an acyclic digraph $G$, let us substitute some of its non-
terminal vertices by strongly connected digraphs that contain directed cycles.
They will form the interior SCCs of the obtained digraph $G^{\prime}$, while
each of the remaining non-terminal vertices of $G$ will form a transient SCC
in $G^{\prime}$.

It seems logical to assign a separate outcome $a$ (resp., $c$) to each
terminal (resp., interior) SCC, thus, getting the set of outcomes
$O=\\{a_{1},\ldots,a_{p}\\}\cup\\{c_{1}\ldots,c_{q}\\}$, which define a DGMS
game. Merging the latter $q$ outcomes in it we obtain a DG game. Obviously,
merging outcomes of a game form respects NS. Hence, an $n$-person DGMS game
may have no NE when $n>2$. The main examples of [7, 2] show this.

Yet, any two-person DGMS game has a NE, which can be determined by a slightly
modified backward induction (BI) procedure [4, Section 1.5]; see also [MN21B,
Section 4.1]. It was proven that finite $n$-person DG and DGMS game forms are
tight, for all $n$. (Note that merging outcomes respects tightness.) Yet,
tightness is equivalent with NS only when $n=2$; for $n>2$ tightness is
neither necessary nor sufficient for NS. Note also that the modified BI works
only for $n=2$ and even in this case the obtained NE may be not subgame
perfect, unlike the NE obtained by the standard BI.

Obviously, contracting each terminal SCC of a DGSM game to a single vertex one
does not change the game. Finally, note that a DGSM game with a unique
interior SCC is DG game.

Conditions (C) and (C22) can be adapted to DGMS games as follows.

$(C^{\prime})$ For any player $i\in I$ every interior SCC $c$ is better than
each terminal SCC $a$.

To formulate $(C^{\prime}22)$ denote by $k(i,c_{j})$ the number of terminal
SCC that are worse than $c_{j}$ for player $i\in I$. Then, (C’22) does not
hold if and only if there are (at least) two distinct players
$i^{\prime},i^{\prime\prime}\in I$ and two, not necessarily distinct, interior
SCC $c_{j^{\prime}}$ and $c_{j^{\prime}}$ such that
$k(i^{\prime},c_{j^{\prime}})\geq 2$ and
$k(i^{\prime\prime},c_{j^{\prime\prime}})\geq 2$.

Obviously $(C^{\prime})$ implies $(C^{\prime}22)$. We conjecture that
$(C^{\prime}22)$ implies NS of finite $n$-person DGMS games (for $n>2$). .

##  3 Subgame perfect NE-free DG games

NE $s=(s_{1},\ldots,s_{n})$ in a finite $n$-person DG game is called uniform
if it is a NE with respect to every initial position $v\in V\setminus V_{T}$.
In the literature uniform NE (UNE) are frequently referred to as subgame
perfect NE. By definition, any UNE is a NE, but not vice versa. A large family
of $n$-person UNE-free DG games satisfying (C) can be found in [5, Section
3.3] for $n>2$, and even for $n=2$ in [1, the last examples in Figures 1 and
3].

Every NE-free game contains a UNE-free subgame [2, Remark 3]. Indeed, consider
an arbitrary NE-free DG game $\Gamma$ and eliminate the initial position
$v_{0}$ from its graph $G$. The obtained subgame $\Gamma^{\prime}$ is UNE-
free. Indeeed, assume for contradiction that $\Gamma^{\prime}$ has a UNE
$s=(s_{1},\ldots,s_{n})$. Then, $\Gamma$ has a NE, which can be obtained by
backward induction. The player beginning in $v_{0}$ chooses a move that
maximizes his/her reward, assuming that $s$ is played in $\Gamma^{\prime}$ by
all players. Clearly $s$ extended by this move forms a NE in $\Gamma$, which
is a contradiction.

Thus, searching for a NE-free DG game (satisfying (C) or (C22)) one should
begin with a UNE-free DG game trying to extend it with an acyclic prefix. This
was successfully reallized in [7, 2], where condition (C22) (not to mention
(C)) was waved. However, under these assumptions all tries failed.

### Acknowledgement

The authors was partially supported by the RSF grant 20-11-20203.

## References

  * [1] Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino, On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games, Discrete Math. 312:4 (2012) 772–788.
  * [2] Endre Boros, Vladimir Gurvich, Martin Milanic, Vladimir Oudalov, and Jernej Vicic, A three-person deterministic graphical game without Nash equilibria, Discrete Applied Math. 243 (2018) 21–38; https://arxiv.org/abs/1610.07701 .
  * [3] Vladimir Gurvich, A four-person chess-like game without Nash equilibria in pure stationary strategies, Business Informatics 1:31 (2015) 68–76.
  * [4] Vladimir Gurvich, Backward induction in presence of cycles, Oxford Journal of Logic and Computation 28:7 (2018) 1635–1646.
  * [5] Vladimir Gurvich and Mariya Naumova, On Nash-solvability of n-person graphical games under Markov’s and a priori realizations; https://arxiv.org/abs/2104.07542
  * [6] Vladimir Gurvich and Mariya Naumova, Polynomial algorithms computing two lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles; https://arxiv.org/abs/2108.05469
  * [7] Vladimir Gurvich and Vladimir Oudalov, A four-person chess-like game without Nash equilibria in pure stationary strategies, https://arxiv.org/abs/1411.0349 [math.CO], 2014.