# Temporal Motifs in Patent Opposition and Collaboration Networks

Penghang Liu  Department of Computer Science and Engineering, State University
of New York at Buffalo, Buffalo, NY, USA  Naoki Masuda  Department of
Mathematics, State University of New York at Buffalo, Buffalo, NY, USA
Computational and Data-Enabled Science and Engineering Program, State
University of New York at Buffalo, Buffalo, NY, USA  Faculty of Science and
Engineering, Waseda University, Tokyo, Japan  Tomomi Kito  Faculty of Science
and Engineering, Waseda University, Tokyo, Japan  Ahmet Erdem Sarıyüce

###### Abstract

Patents are intellectual properties that reflect innovative activities of
companies and organizations. The literature is rich with the studies that
analyze the citations among the patents and the collaboration relations among
companies that own the patents. However, the adversarial relations between the
patent owners are not as well investigated. One proxy to model such relations
is the patent opposition, which is a legal activity in which a company
challenges the validity of a patent. Characterizing the patent oppositions,
collaborations, and the interplay between them can help better understand the
companies’ business strategies. Temporality matters in this context as the
order and frequency of oppositions and collaborations characterize their
interplay. In this study, we construct a two-layer temporal network to model
the patent oppositions and collaborations among the companies. We utilize
temporal motifs to analyze the oppositions and collaborations from structural
and temporal perspectives. We first characterize the frequent motifs in patent
oppositions and investigate how often the companies of different sizes attack
other companies. We show that large companies tend to engage in opposition
with multiple companies. Then we analyze the temporal interplay between
collaborations and oppositions. We find that two adversarial companies are
more likely to collaborate in the future than two collaborating companies
oppose each other in the future.

## Introduction

Innovative activities of companies and organizations are often reflected by
patents. Once a patent is granted, the owner receives a temporary right to
legally exclude others from making, using, or selling an invention. Therefore,
managing patents is a crucial aspect in enhancing the competitiveness of
companies. Thanks to the recent advances in computer and data science, large-
scale patent data have been analyzed with the aim to understand innovation
processes [1, 2].

Many studies have investigated the network of patents, in order to understand
the evolution of technology and assess the values of inventions [3, 4, 5, 6,
7]. In a patent citation network, patents are connected via citations, and the
technological importance of a patent is often measured by its number of
citations received. Patents can also reflect the relations between the patent
owners. Co-ownership of patents by multiple companies implies collaborative
relations among them. Considerable efforts have been made to analyze the
patent collaboration networks, in which the edges are positive and symmetric
relationships rather than citation relationships, and discover the factors
that lead to collaborations among companies [8, 9, 10]. However, the rival or
adversarial relations among patent owners have not been addressed as much. The
adversarial relations among companies can be captured by patent opposition,
which is a legal activity in which a company challenges the validity of a
patent in usually 6-9 months after the grant date. Since the challenged patent
may be revoked if the opposition is successful, companies often oppose the
patents owned by rival companies to try to hinder their innovation activities
[11, 12, 13]. In a recent study, Kito et al. [14] constructed a network of
companies and analyzed adversarial relationships in patent networks. They
investigated the global and local statistics of a patent opposition network
and applied network motif analysis among other things. However, the interplay
between patent oppositions and collaborations, especially the temporal
correlation between them, has not thoroughly been studied.

The business relations among companies are highly intricate, where rivalries
and cooperations are both common and heavily intertwined with each other. Our
goal is to characterize the patent oppositions, collaborations, and the
interplay between them which may help us understand how companies interact
with each other and strategize their business decisions. While there may exist
other methods to achieve this, potentially including various social physics
approaches [15], network-based approaches have been shown to give promising
results [14]. In this work, we embrace network-based analysis and specialize
on temporal aspects of the networks. Temporal network analysis is expected to
be a useful approach in this context for two reasons: (1) the relations among
companies often change over time, and it is not possible to understand their
dynamic structure via the static network representation; and (2) a company’s
business strategy is reflected by its reactions to the previous oppositions
and collaborations, the understanding of which requires the knowledge of the
chronological order and the time difference between oppositions and
collaborations.

Network motifs are defined as statistically overrepresented subgraphs [16],
which are often used for examining interactions among small sets of nodes in
the networks. Several models have been proposed for motifs in temporal
networks [17, 18, 19, 20], which we compared in a recent survey [21] and were
also partially covered in earlier work [22, 23]. Temporal motif analysis has
been shown to be a versatile tool for many applications including cattle trade
movements [24], editor interactions in Wikipedia [25], mobile communication
networks [26, 27], and human interactions [28] (In the following text, for the
sake of simplicity, we follow the recent literature on temporal motifs [20,
21] to refer to all temporal network patterns of limited size as motifs, not
only the overrepresented patterns as suggested by Milo et al. [16].)

In this study, we construct a two-layer temporal network to model the patent
oppositions and collaborations from 1978 to 2018. We deploy temporal motifs to
analyze the oppositions and collaborations from structural and temporal
perspectives. Our analysis is two-fold. First, we identify frequent temporal
motifs in patent oppositions using different timing parameters and then
investigate the sizes of the companies to further understand the opposition
relations. Second, we identify the collaborations between the companies in the
detected opposition motifs and investigate the interplay between oppositions
and collaborations.

## Methods

### Patent opposition and collaboration network

(a)  (b)

Figure 1: (a) An example for patent oppositions and collaborations. Company A
opposes a patent owned by company B at $t_{1}$, and then companies A and C co-
own a patent at $t_{2}$, which is opposed by company B at $t_{3}$. (b) The
corresponding patent network. The directed solid lines represent patent
oppositions. The undirected dashed line represents the collaboration.

We explore temporal networks that we represent as $G=(V,E)$, where $V$ is the
set of nodes, and $E$ is the set of time-stamped events. Each event $e_{i}\in
E$ is a 3-tuple $(u_{i},v_{i},t_{i})$ [29]], which represents a directed
relation from the source node $u_{i}$ to the target node $v_{i}$ that occurs
at time $t_{i}$. The set $E$ is a time-ordered list of $k$ events such that
$t_{1}\leq t_{2}\leq t_{3}\leq\cdots\leq t_{k}$. Here we distinguish edges and
events, where the edge $(u,v)$ is the static projection of an event $(u,v,t)$,
and there may be multiple events on an edge. We restrict ourselves to
opposition events in our temporal motif analysis. We consider collaboration
events only within the context of temporal opposition motifs.

We represent the two-layer temporal network of patent oppositions and
collaborations as $G=(V,E_{O},E_{C})$, where $V$ is the set of nodes
representing the companies. The event set $E_{O}$ defines the opposition
layer, in which each event $(u,v,t)\in E_{O}$ indicates a directed relation
that company $u$ opposed a patent owned by company $v$ at time $t$. The event
set $E_{C}$ defines the collaboration layer, in which each event
$(v_{1},v_{2},t)\in E_{C}$ indicates an undirected relation that company
$v_{1}$ and company $v_{2}$ have co-owned a patent since time $t$. We consider
a patent is owned by a company since time $t$ if either the patent is granted
to the company at $t$ or the patent is transferred to the company at $t$.
Figure 1 shows an example for patent oppositions and collaborations among
three companies: company A opposes company B at time $t_{1}$, company A and C
collaborate at time $t_{2}$, and then company B opposes company A and C at
time $t_{3}$. Note that the patent oppositions and collaborations can also be
represented as a signed network. For example, Park et al. analyze the motifs
in a signed directed friendship network [30]. However, we represent the patent
oppositions and collaborations as a two-layer network rather than a signed
network because there may be both opposition and collaboration between the
same pair of nodes, which cannot be addressed by a signed network.

We use a previously collected patent data from Orbis Database [31] and Orbis
Intellectual Property Database [32]. We show properities of the two-layer
temporal network of patent oppositions and collaborations in Table 1. The data
contains 11,317 companies, 26,433 oppositions, and 1,554 collaborations. There
are 14,320 and 1,009 edges in the static projection of the opposition and
collaboration layers, respectively, which indicates that there are repetitive
oppositions and collaborations among the companies. The low average degree
indicates that the two-layer network is sparse. However, there is a giant
connected component in the static projection of the opposition network which
contains 66% of nodes and 81% of edges, and all the other components have less
than 10 nodes. Kito et al. [14] show that many companies own and oppose
patents in multiple industrial fields. Hence the network of patent oppositions
and collaborations is not segregated with respect to technical domains but
rather heavily intertwined.

Layer | # nodes | # edges | # events | Time span
---|---|---|---|---
Opposition | 11,317 | 14,320 | 26,433 | 2/25/1981 - 4/19/2018
Collaboration | 11,317 | 1,009 | 1,554 | 6/23/1978 - 1/10/2018
Table 1: Properties of the two-layer temporal network of patent oppositions
and collaborations.

### Motifs in temporal networks

In this study, we consider two types of timing thresholds for temporal motifs:
The inter-event time threshold limits the time difference between any pair of
consecutive events in the motif, and the time-window threshold requires all
the events to occur within a given time interval. Formally, given a temporal
network $G=(V,E)$ and two timing thresholds $\Delta_{C}$ and $\Delta_{W}$,
which we refer to as the inter-event time threshold and time-window threshold,
respectively, an $n$-node $m$-event (with $n\geq 2$ and $m\geq 2$) motif
$M=(V^{\prime},E^{\prime})$, where
$E^{\prime}=\\{(u^{\prime}_{1},v^{\prime}_{1},t^{\prime}_{1}),\ldots,(u^{\prime}_{m},v^{\prime}_{m},t^{\prime}_{m})\\}$
and $t^{\prime}_{1}\leq t^{\prime}_{2}\leq\cdots\leq t^{\prime}_{m}$, is a
temporal subgraph of $G$ such that

  * •

$|V^{\prime}|=n$, $|E^{\prime}|=m$, $V^{\prime}\subseteq V$, and
$E^{\prime}\subseteq E$.

  * •

For any pair of consecutive events
$(u^{\prime}_{i},v^{\prime}_{i},t^{\prime}_{i})\in E^{\prime}$ and
$(u^{\prime}_{i+1},v^{\prime}_{i+1},t^{\prime}_{i+1})\in E^{\prime}$ such that
{$u^{\prime}_{i},v^{\prime}_{i}\\}\cap\\{u^{\prime}_{i+1},v^{\prime}_{i+1}\\}\neq\emptyset$,
it holds true that $t^{\prime}_{i+1}-t^{\prime}_{i}\leq\Delta_{C}$.

  * •

For the first and the last events
$(u^{\prime}_{1},v^{\prime}_{1},t^{\prime}_{1})\in E^{\prime}$ and
$(u^{\prime}_{m},v^{\prime}_{m},t^{\prime}_{m})\in E^{\prime}$, it holds true
that $t^{\prime}_{m}-t^{\prime}_{1}\leq\Delta_{W}$.

  * •

For any pair of events $(u^{\prime},v^{\prime},t^{\prime})\in E^{\prime}$ and
$(u^{\prime\prime},v^{\prime\prime},t^{\prime\prime})\in E^{\prime}$,
$t^{\prime}\neq t^{\prime\prime}$.

The last statement in the case of the opposition network requires all
oppositions in the motif to have unique timestamps. This is because if an
opposed patent is owned by several companies, an opposition event from the
opposing company to each of the owner companies occurs at the same time.
Allowing these opposition events to belong to the same motif is not helpful
since they provide redundant information from the same patent opposition.

| (a)
---
(b)
(c)
Figure 2: (a) All 2-event motifs, which are time-ordered event pairs. (b) Two
examples of 3-event motifs labeled by the sequence of two 2-event pairs. (c)
All 2-node 3-event and 3-node 3-event motifs. R stands for repetition, P for
ping-pong, I for in-burst, O for out-burst, C for convey, and W for weakly-
connected.

A pair of events, i.e., 2-event motif, is the simplest temporal motif
according to our definition. Figure 2(a) shows all types of 2-event motifs.
Note that 2-node 2-event motifs are either a repetition, in which the two
events occur in the same direction, or a ping-pong, in which the two events
occur in the reciprocal directions. There are four types of 3-node 2-event
motifs; in an in-burst motif, the two events share the same source; in an out-
burst motif, the two events share the same target; in a convey motif, the
source of the second event is the target of the first event; and in a weakly-
connected motif, the target of the second event is the source of the first
event.

A 3-event motif is composed of two event pairs, i.e., the pair composed of the
first and second events and the pair composed of the second and third events.
Therefore, each 3-event motif can be represented as a sequence of two event
pairs. Figure 2(b) gives two examples: a 3-node 3-event motif can be
represented as a sequence of ping-pong and out-burst (denoted as P-O for
convenience), while a 3-node cycle can be represented as a sequence of convey
and convey (C-C). There are 4 types of 2-node 3-event motifs and 32 types of
3-node 3-event motifs (shown in Figure 2(c)). Among the 32 types of 3-node
3-event motifs, eight motifs are triangle motifs, of which the static
projection when one ignores the direction of the edges is a closed triangle.
The other 24 motifs are wedge motifs, of which the static projection is an
open triangle (i.e., wedge). Among the triangle motifs, two of them are 3-node
cycles, of which the static projection is a directed cycle, and the other six
are acyclic triangle motifs.

### Significance of temporal motifs

In static motif analyses, randomized networks are used as null models to
measure the statistical significance of motifs. Milo et al. [16] analyzed the
significance of motifs using the directed configuration model, which yields
randomized networks that conserve the in-degree and out-degree of each node in
the original network. One measures the statistical significance of motif
$M_{i}$ by the $Z$ score defined as
$Z_{i}=\frac{Original_{i}-\mu_{i}}{\sigma_{i}}$, where $Original_{i}$ is the
number of $M_{i}$ motifs in the original data, and $\mu_{i}$ and $\sigma_{i}$
are the mean and standard deviation of the number of $M_{i}$ motifs computed
from a given number of samples of randomized networks. For temporal networks,
there are numerous reference models that randomize different structural or
temporal aspects of the given temporal netowrk [33]. We consider the following
randomization methods to measure the $Z$ score for the temporal motifs:

  * •

Link shuffling (LS) randomizes the edges using the Erdős-Rényi random graph
model. The events and their timestamps are preserved for each edge.

  * •

Degree-constrained link shuffling (DCLS) randomizes the edges using the
directed configuration model, which conserves the in-degree and out-degree of
each node. The events and their timestamps are preserved for each edge.

  * •

Weight-constrained timeline shuffling (WTS) randomly generates the timestamps
of all events for each edge. The number of events on each edge and the
structure of the static network are preserved. The WTS corresponds to the
assumption that a Poisson process generates the events on each edge, which is
equivalent to randomly and independently assigning the timestamp of each event
from the uniform distribution on the observation time window.

  * •

Inter-event shuffling (IS) uniformly randomly shuffles the inter-event times
on each edge while keeping the time of the first and the last event fixed. The
number of events on each edge and the structure of the static network are
preserved.

  * •

Timestamp shuffling (TS) uniformly randomly shuffles the timestamps of all
events regardless of the edges that the events belong to. The number of events
on each edge and the structure of the static network are preserved.

LS and DCLS randomize edges and hence the structure of the static network, but
not the temporal features. In contrast, WTS, IS, and TS randomize event times
without changing the structure of the static network.

## Results

In this section, we examine temporal patterns in patent oppositions,
collaborations, and the interplay between them. First, we find the temporal
motifs in patent oppositions using different timing thresholds and investigate
the sizes of the companies in the opposition motifs. Second, we identify
collaborations that exist between any pair of companies in the detected
opposition motifs. Then, we analyze the interplay between patent oppositions
and collaborations from both structural and temporal perspectives.

Figure 3: The number of 2-event motifs in the opposition network using
different timing thresholds. Each row represents a type of 2-event motif; see
the caption of Figure 2 for the abbreviation. The color indicates the motif
counts. For each heat map $(x,y]$, we only count the motifs of which the
inter-event time is larger than $x$ and not greater than $y$.

### Motifs in patent oppositions

We first explore the temporal motifs in patent oppositions. In particular, we
want to answer the following questions: 1) What are the frequent patterns in
patent oppositions for a given timing threshold? 2) How does the size of the
companies impact their roles in the patent oppositions?

(a)  (b)

Figure 4: The number of 2-node 3-event and 3-node 3-event motifs in the
opposition network for a range of $\Delta_{C}$ values (a) or for a range of
$\Delta_{W}$ values (b). For each heatmap, $(x,y]$ indicates the values of the
timing threshold, i.e., we only count the motifs for which
$\Delta_{C}\in(x,y]$ and $\Delta_{W}=10$ years in panel (a), and
$\Delta_{C}=\Delta_{W}\in(x,y]$ in panel (b). Each cell in the heat map
corresponds to a type of 3-event motif, where the row shows the first pair of
events (i.e., the first two of the three events constituting the 3-event
motif) and the column shows the second pair of events (i.e., the second and
third events in the same motif). The color indicates the motif counts.

#### Frequent patterns in patent oppositions

We first investigate the number of 2-event motifs in the opposition network.
Note that the two timing thresholds, $\Delta_{C}$ and $\Delta_{W}$, are
equivalent for 2-event motifs since the inter-event time of a 2-event motif is
equal to its timespan. We select six timing thresholds and count the numbers
of motifs for each timing threshold. The results shown in Figure 3 indicate
that the repetition motifs are more abundant than the ping-pong motifs. This
result indicates that patent oppositions are more like one-way attack rather
than a fight between two; a company may consistently oppose its opponent many
times, but a company being opposed relatively infrequently opposes back. In-
burst and out-burst motifs are the most frequently observed among the six
types of 2-event motifs. This result suggests that companies tend to oppose or
be opposed by multiple companies within a short time. Regarding the motif
counts across different timing thresholds, in-burst and out-burst motifs are
consistently the most abundant. Then comes the convey motifs, where an opposed
company copies the behavior to hinder others, and weakly-connected motifs,
where an opposer company triggers an opposition to itself. Repetition and
ping-pong motifs are the least abundant but their fractions among the 2-event
motifs are slightly larger for small timing thresholds. The ranking of the six
types of motif counts is the same for all the timing thresholds, except
$(0yr,1yr]$ where the weakly-connected motifs are observed less frequently
than the convey motifs.

(a)  (b)

Figure 5: The three most significant (a) and the three least significant (b)
3-event motifs based on the $Z$ score. The numbers shown are the Z scores. We
used the WTS model as null model and set $\Delta_{W}=10$ years.

Next, we count the numbers of 2-node 3-event and 3-node 3-event motifs for
$\Delta_{C}$, $\Delta_{W}$$=1,2,3,4,5,$ and $10$ years. We first set
$\Delta_{W}=10$ years and consider a range of $\Delta_{C}$ values. Then, we
set $\Delta_{C}=\Delta_{W}$ for a range of $\Delta_{W}$ values (i.e., we only
consider the time-window threshold and do not enforce the inter-event timing
threshold). The numbers of motifs of each case are shown in Figure 4. We
observe the following patterns consistently for the different timing threshold
values. First, the motifs containing in-bursts and out-bursts are dominant.
Second, motifs containing repetitions are more abundant than those containing
ping-pongs. Third, the 2-node 3-event motifs (i.e., R-R, R-P, P-R, P-P) are
progressively less abundant than the 3-node 3-event motifs when $\Delta_{C}$
or $\Delta_{W}$ is larger. These three results are consistent with the results
for 2-event motifs shown in Figure 3. Fourth, triangle motifs are relatively
rare. There are eight types of triangle motifs but they only occupy 3% of the
total motif count when $\Delta_{C}=$ 1 year, for example. The last result is
coherent with the structural balance theory [34, 35]. Because patent
oppositions are negative relations, the triangle of oppositions is an
imbalanced structure. In addition, the 3-node cycles, i.e., C-C and W-W
motifs, appear less frequently than the other six acyclic triangle motifs. A
similar pattern has been found in static social networks where a negative edge
is less likely to occur with two other negative edges in a cycle [36].

In addition to the motif counts, we measure the statistical significance of
each type of opposition motif using different null models. To this end, we
generate 10 random graphs for each null model and compute the $Z$ score for
each type of opposition motif (see Supplementary Table 1). For the LS and DCLS
null models, some motifs are not observed at all or have zero variation across
different realizations of the randomized network. The Z scores are positively
large, safely significantly so after controlling for multiple comparison
(i.e., > 10), for all the 2-node 2-event motifs and 3-node 2-event motifs for
the WTS and TS. Figure 5 shows the most and the least significant opposition
motifs using the WTS as null model and $\Delta_{W}=10$ years. The WTS model
uniformly randomly generates the timestamps for all events assuming that
events are generated by a Poisson process on each edge. The three most
significant motifs include wedge motifs that contain in-bursts and repetitions
(I-R, W-I, R-I), while the three least significant motifs contain two 3-node
cycles (O-W, C-C, W-W). These results justify our analysis stated earlier in
this section based on the motif counts: the motifs containing repetitions and
in-bursts tend to be frequent, whereas the cycle motifs are relatively scarce.

Figure 6: The distribution of the number of patents owned by the companies.  Motif |  |  |
---|---|---|---
Mean |  Median |  Std |  Mean |  Median |  Std |  Mean |  Median |  Std
|  9227.7 |  6523 |  19142.0 |  8943.5 |  2232 |  23997.9 | N/A
|  7305.7 |  5812 |  8598.0 |  7703.5 |  6523 |  10469.7 | N/A
|  5194.5 |  342 |  24176.1 |  8102.8 |  394 |  28014.7 |  4867.6 |  248 |  18135.4
|  18388.7 |  12313 |  39151.5 |  8625.8 |  493 |  35229.4 |  9638.1 |  775 |  36575.8
|  16064.3 |  12313 |  30410.0 |  3949.6 |  479 |  9403.3 |  9111.7 |  1195 |  31176.3
|  20309.1 |  12313 |  39205.7 |  8638.2 |  503 |  35458.6 |  3606.2 |  354 |  9143.4
Table 2: Size of the company for each node in the 2-event opposition motifs.
We show the mean, median, and standard deviation (denoted by Std in the table)
of the number of patents owned by the companies for each node in a given type
of motif. For the entire network, the opposer and opposed companies have
4119.9 and 6492.8 patents on average, respectively.

#### Position of companies of different sizes in the opposition motifs

Companies of different sizes may participate in temporal network motifs by
occupying particular positions in the motif. To explore this possibility, we
examine the relationship between the sizes of the companies and their
positions within the opposition motifs. For simplicity, we define the size of
a company by the number of patents that the company owns. Note that this is
often much greater than the number of patents involved in the oppositions. The
mean and median of the numbers of patents owned by the companies are 959.07
and 25, respectively, while the minimum and maximum are 0 and 494,463,
respectively. We show the distribution of the number of owned patents in
Figure 6. We identify all 2-event motifs with $\Delta_{C}=\Delta_{W}=$ 10
years in the opposition network.

For each position in each type of opposition motif, we show the mean, median,
and the standard deviation of the number of patents owned by those companies
in Table 2. Considering the opposer and opposed company pairs in all the
opposition events, the mean of the number of patents owned by the opposers is
4119, the median is 162, and the standard deviation is 18330. For opposed
companies, the mean of the number of patents owned is 6492, the median is 214,
and the standard deviation is 31427. Although the mean size of the company
does not significantly depend on the position in the motif due to a relatively
large standard deviation, we observe the following tendencies. First, the
result for repetition and ping-pong motifs suggests that the two companies
forming the motif tend to have similar sizes. In the in-burst motifs, the
opposed company is smaller than the first opposer but larger than the second
opposer. In the out-burst motifs, the opposer company is larger than the
opposed companies. In the convey and weakly-connected motifs, the center
company (which opposes and is opposed) is substantially larger than the other
two companies. In almost all positions, the companies that are involved in
opposition motifs are larger than the average company in the network. Second,
in most motifs, the opposer companies are larger than the average opposer in
the network, with the exception of first opposers in convey and weakly-
connected motifs. The opposer company in the out-burst motifs and the center
company in the convey and weakly-connected motifs tend to be particularly
large. Third, among the companies which only oppose one company and are not
opposed by any company within the motif (i.e., the opposers in the in-burst
and each opposer in the convey and weakly-connected motifs), the opposers in
the in-burst motifs tend to be larger than the other two. Interestingly, the
first opposer in the in-burst motif tends to be larger than the second
opposer. The companies which are only opposed by one company and do not oppose
any company within the motif (i.e., the two opposed companies in the out-burst
and each opposed company in the convey and weakly-connected motifs) have
similar sizes. Fourth, among the companies that oppose twice and are not
opposed by any, the opposer company in the out-burst motifs is substantially
larger than the opposer in the repetition motifs on average. Among the
companies that are opposed twice and do not oppose any, the opposed company in
the in-burst motifs is smaller than the opposed company in the repetition
motifs. These results suggest that the large companies tend to oppose multiple
companies rather than the same company multiple times and that they are more
likely to be opposed by one company multiple times than opposed by multiple
companies. Lastly, among the companies that oppose only one company and is
opposed by only one company (i.e., both companies in the ping-pong and the
center companies in the convey and weakly-connected motifs), the ones in the
convey and weakly-connected are substantially larger than the companies in the
ping-pong motifs on average. This result suggests that the large companies
tend to engage with multiple companies rather than the same company multiple
times.

To validate whether our findings are unique to temporal motifs, we also carry
out a similar analysis for static motifs in the static network of patent
oppositions. We show the results in Table 3. For each position in each motif,
the standard deviation of the company size in static motifs is considerably
larger than in temporal motifs. This result suggests that the tendencies in
the static motifs are less consistent. Another observation is that the size of
the companies in static in-burst motifs shows a different behavior than in
temporal motifs: the opposed company tends to be larger than the other two
opposer companies. In sum, the tendencies of company sizes we observed in the
temporal motifs are not just consequences of the structure of the static
networks, but rather are affected by the temporal relationships among patent
oppositions.

Motif |  |  |
---|---|---|---
Mean |  Median |  Std |  Mean |  Median |  Std |  Mean |  Median |  Std
|  4127.6 |  431.5 |  15589.5 | N/A | N/A
|  7939.4 |  329 |  33576.4 |  2924.9 |  128 |  14603.6 | N/A
|  18812.1 |  2492 |  45090.4 |  8490.0 |  202 |  41724.4 | N/A
|  46558.6 |  12313 |  68205.2 |  2594.6 |  138 |  13102.2 |  10924.6 |  238 |  50504.6
Table 3: Size of the company for each node in the static opposition motifs. We
show the mean, median, and standard deviation of the number of patents owned
by the companies for each node in a given type of motif. Although the order of
the events is irrelevant in static motifs, we use the same notations as those
for the temporal motifs for easing the comparison with Table 2. In static
motifs there is no repetition (therefore, no presence of R in this table), and
convey and weakly-connected are the same. It should also be noted that we do
not distinguish the two nodes in the ping-pong motif because of the absence of
the timing information.

### Collaborations within opposition motifs

Now we explore the interplay between patent collaborations and oppositions by
looking at the 2-event opposition motifs found with $\Delta_{W}=$ 10 years.
For each opposition motif $M=(V^{\prime},E^{\prime})$ where
$E^{\prime}=\\{(u^{\prime}_{1},v^{\prime}_{1},t^{\prime}_{1}),(u^{\prime}_{2},v^{\prime}_{2},t^{\prime}_{2})\\}$,
we examine all the collaboration events $(a,b,t)$ such that $a,b\in
V^{\prime}$ and $t^{\prime}_{1}-10[yr]\leq t\leq t^{\prime}_{2}+10[yr]$.
Specifically, we aim to address three questions: 1) How many collaborations do
we observe for a given type of opposition motif? 2) Between which two
companies do we often observe collaboration? 3) When does collaboration occur
and how are they related to the timing of oppositions?

#### Number of collaborations in opposition motifs

To address the first question, we count the number of collaborations between
each pair of companies in each 2-event opposition motif. The results are shown
in Table 4. Generally, we only observe collaborations in a small fraction of
the opposition motifs. This is because that the total number of collaborations
is much smaller than the total number of oppositions (see Table 1). Note that
we do not observe any collaborations between two companies that have opposed
each other (i.e., ping-pong motifs). Table 4 also indicates that
collaborations are substantially more frequent in out-burst and convey motifs
than in in-burst and weakly-connected motifs. We also observe that there are
only three out of 475,429 out-burst motifs with 2 collaborations, and that
there is no more than one collaboration in any other types of 2-event motif.
In addition, although the convey and weakly-connected motifs have the same
static structure, the likelihood of collaboration is higher in the convey than
weakly-connected motifs. This may be because the two oppositions occur in a
non-transitive way in the weakly-connected motifs, and therefore the two nodes
with no opposition relation are more likely to be unrelated. In contrast, the
two oppositions occur in a transitive manner in convey motifs. The scarcity of
multiple collaborations is also observed in the 3-event opposition motifs;
more than 91% of them do not have any collaborations (see Supplementary Table
2).

Motif | Motif count | Number of collaborations in the motif
---|---|---
0 |  1 |  2 |  3
| 55,458 |  99.9% |  0.01% |  N/A |  N/A
| 8,418 |  100% |  0% |  N/A |  N/A
| 1,150,097 |  99.7% |  0.22% |  0% |  0%
| 475,429 |  97.2% |  2.73% |  $<$0.01% |  0%
| 125,298 |  98.6% |  1.36% |  0% |  0%
| 151,335 |  99.2% |  0.76% |  0% |  0%
Table 4: The number of collaborations observed in each 2-event opposition
motif. Here we show the total count of each motif and the fraction of the
opposition motifs with 0, 1, 2, and 3 collaborations.  Figure 7: Fractions of
the node pairs between which the collaborations occur in 3-node 2-event
opposition motifs.

#### Companies involved in the collaborations

Patent opposition and collaboration are not exclusive actions. They may occur
between the same pair of companies because they may collaborate in one field
and compete in another field for strategic reasons. To examine this
possibility, we investigate which two companies that belong to the same motif
are more likely to collaborate with each other. We exclude the 2-node
opposition motifs (i.e., repetition and ping-pong) from the following analysis
because 2-node motifs only involve two companies such that which pair of
companies in the motif tends to collaborate is an irrelevant question.

Figure 7 shows the fractions of collaborations between each pair of companies
in each type of 3-node 2-event opposition motif with at least one
collaboration. We find that collaborations tend to occur between the companies
that have no opposition relation with each other. For example, in out-burst
motifs, 96.3% of the collaborations occur between the two nodes that have no
opposition relationship. In other words, two companies opposed by the same
company are more likely to collaborate than otherwise. Such a tendency is also
present in in-burst motifs, where the two companies opposing the same company
tend to collaborate with each other, but to a lesser extent (75.4%) than in
the case of out-burst motifs. The likelihood of collaboration between the two
companies with no opposition relation is larger in convey motifs than in
weakly-connected motifs. This result may be due to the presence and absence of
the transitive relationship of oppositions in the convey and weakly-connected
motif, respectively.

Motif |  |  |
---|---|---|---
Before |  Between |  After |  Before |  Between |  After |  Before |  Between |  After
|  36.1% |  12.7% |  51.06% |  17.6% |  19.5% |  62.8% |  44.7% |  27.7% |  27.5%
|  48.8% |  15.9% |  35.2% |  35.5% |  16.6% |  47.8% |  41.4% |  34.8% |  23.6%
|  13.0% |  34.7% |  52.1% |  20.0% |  40.0% |  40.0% |  38.7% |  34.4% |  26.8%
|  11.8% |  17.2% |  70.9% |  18.6% |  66.1% |  15.2% |  44.2% |  36.0% |  19.7%
Table 5: Timing of collaboration events occurring on top of opposition motifs.
For each type of opposition motif and each edge in the motif, we show the
fraction of collaborations that occur before all oppositions, between the two
oppositions, and after all oppositions. The collaborations between two nodes
with an opposition relation tend to occur after all opposition events (red),
whereas the collaborations between two nodes with no opposition relation tend
to occur before all opposition events (blue).

#### Timing of the collaborations

Are collaboration events induced by the organization of opposition edges that
are already existing or vice versa? To try to address this question, we
investigate the temporal interrelations between opposition and collaboration
events. For a given type of 2-event opposition motif, we compute the fraction
of the collaboration events occurring in three time intervals: (1) before the
two opposition events, (2) between the two opposition events, and (3) after
the two opposition events. We exclude the repetition and ping-pong opposition
motifs from this analysis because there are a few collaboration events on top
of the former and no collaboration event on top of the latter. The results,
shown in Table 5, indicate that, for the two companies that do not have
opposition relations, the collaborations tend to happen before the two
oppositions (shown in blue in Table 5). In other words, for two collaborating
companies that share a common adversary, the collaborations between them tend
to occur before they oppose or are opposed by a common company than vice
versa. In addition, for two companies that have both opposition and
collaboration relations, while their fraction is small (see Figure 7), the
collaborations tend to occur after the two opposition events (shown in red in
Table 5). This result suggests that two adversarial companies are more likely
to collaborate in the future than two collaborating companies oppose each
other in the future.

Note that although the time intervals (i.e., before, between, and after) have
the same upper bound (i.e., 10 years) as mentioned at the beginning of the
section, the exact lengths of the intervals vary across the types of interval
and types of motif. For instance the mean interval length between the
opposition events is around 3.9 to 4.5 years for all the motifs, which is
usually smaller than the intervals before or after the two oppositions. To
calibrate for this effect, we divide each fraction in Table 5 by the mean
interval length for each case to find fraction-per-year values. The results
shown in Table 6 support the trends found with Table 5 albeit less strongly.
In other words, collaboration between non-opposing companies tends to occur
before the opposition events with a third company than after them, whereas the
largest fraction-per-year collaboration between non-opposing companies occurs
between the two opposition events (see the last three columns of Table 6).
Table 6 also suggests that collaboration on an edge with an opposition event
tends to occur after the two opposition events constituting the motif than
before them (see the first six columns).

Motif |  |  |
---|---|---|---
Before |  Between |  After |  Before |  Between |  After |  Before |  Between |  After
|  4.32% |  2.96% |  5.38% |  2.10% |  4.54% |  6.61% |  5.34% |  6.45% |  2.90%
|  5.23% |  4.06% |  4.89% |  3.80% |  4.24% |  6.64% |  4.44% |  8.89% |  3.28%
|  1.35% |  8.34% |  7.63% |  2.08% |  9.62% |  2.93% |  4.02% |  8.27% |  3.93%
|  1.22% |  3.76% |  9.99% |  1.92% |  14.46% |  2.14% |  4.55% |  7.88% |  2.78%
Table 6: Normalized timing of collaboration events occurring on top of
opposition motifs. For each type of opposition motif and each edge in the
motif, we show the fraction of collaborations per year that occur before all
oppositions, between the two oppositions, and after all oppositions. For each
interval, the fraction is normalized by the length of the interval.

## Discussion

We studied the adversarial and collaborative relations between the patent
holder companies. We first analyzed the frequency of patent oppositions and
showed that (1) the oppositions tend to be more repetitive than reciprocal;
(2) different timing thresholds between the oppositions present a consistent
behavior in the ranking of 2-event and 3-event motif types; and (3)
oppositions exhibit coherent results with the structural balance theory. We
also measured the statistical significance of opposition motif frequencies
using different null models and showed that the motifs containing repetitions
and in-bursts tend to be abundant, whereas the ping-pong and triangle motifs
are scarce. Our analysis of the company sizes in the opposition motifs showed
that (1) the opposer companies tend to be larger than the opposed companies in
most 2-event motifs; and (2) large companies are likely to be engaged in
oppositions with multiple companies. In our analysis on the interplay between
collaborations and oppositions, we found that (1) collaborations tend to occur
between the companies that have no opposition relation with each other; (2)
for two collaborating companies that share a common adversary, the
collaborations between them tend to occur before they oppose or are opposed by
a common company than vice versa; and (3) two adversarial companies are more
likely to collaborate in the future than two collaborating companies oppose
each other in the future.

One limitation of our work is that we considered only the 2-event and 3-event
motifs with up to 3 nodes. Extending the size of the motifs may reveal new
insights regarding the correlation and interplay between collaborations and
oppositions. Moreover, the nodes in the motifs can be enriched with the
country and sector information of the companies, and the events in the motifs
can be enhanced by the features of the patent and opposition texts. Such
information can potentially lead to a more holistic assessment of oppositions
and collaborations.

Another potential opportunity for future research is designing new null models
for temporal networks. In our analysis, all the null models yielded largely
positive $Z$ scores—the counts in the empirical networks are always larger
than those in the null models. Choosing a proper null model is already
challenging for static networks [37] and the problem is even more difficult
for temporal networks due to the intertwined temporal and structural
complexity [17, 33]. Deploying and assessing null models for a more rigorous
measurement of the statistical significance of temporal motifs also warrants
future work.

## References

  * [1] Youn, H., Strumsky, D., Bettencourt, L. M. & Lobo, J.  Invention as a combinatorial process: evidence from us patents.  _Journal of the R. Society Interface_ 12, 20150272, https://doi.org/10.1098/rsif.2015.0272 (2015).
  * [2] Hasan, I. & Tucci, C. L.  The innovation–economic growth nexus: Global evidence.  _Research Policy_ 39, 1264–1276, https://doi.org/10.1016/j.respol.2010.07.005 (2010).
  * [3] Gao, Y., Zhu, Z., Kali, R. & Riccaboni, M.  Community evolution in patent networks: technological change and network dynamics.  _Applied Network Science_ 3, 1–23, https://doi.org/10.1007/s41109-018-0090-3 (2018).
  * [4] Verspagen, B.  Mapping technological trajectories as patent citation networks: A study on the history of fuel cell research.  _Advances in Complex Systems_ 10, 93–115, https://doi.org/10.1142/S0219525907000945 (2007).
  * [5] Funk, R. J. & Owen-Smith, J.  A dynamic network measure of technological change.  _Management Science_ 63, 791–817, https://doi.org/10.1287/mnsc.2015.2366 (2017).
  * [6] Érdi, P. _et al._ Prediction of emerging technologies based on analysis of the us patent citation network.  _Scientometrics_ 95, 225–242, https://doi.org/10.1007/s11192-012-0796-4 (2013).
  * [7] Acemoglu, D., Akcigit, U. & Kerr, W. R.  Innovation network.  _Proceedings of the National Academy of Sciences USA_ 113, 11483–11488, https://doi.org/10.1073/pnas.1613559113 (2016).
  * [8] Balconi, M., Breschi, S. & Lissoni, F.  Networks of inventors and the role of academia: An exploration of Italian patent data.  _Research Policy_ 33, 127–145, https://doi.org/10.1016/S0048-7333(03)00108-2 (2004).
  * [9] Fleming, L., Mingo, S. & Chen, D.  Collaborative brokerage, generative creativity, and creative success.  _Administrative Science Quarterly_ 52, 443–475, https://doi.org/10.2189/asqu.52.3.443 (2007).
  * [10] Graf, H.  Gatekeepers in regional networks of innovators.  _Cambridge Journal of Economics_ 35, 173–198, https://doi.org/10.1093/cje/beq001 (2010).
  * [11] Helmers, C. _et al._ _The Economic Analysis Of Patent Litigation Data_ , vol. 48 (WIPO, Geneva, 2018).
  * [12] Sterlacchini, A.  Patent oppositions and opposition outcomes: Evidence from domestic appliance companies.  _European Journal of Law and Economics_ 41, 183–203, https://doi.org/10.1007/s10657-015-9494-z (2016).
  * [13] Cremers, K., Harhoff, D., Scherer, F. & Vopel, K.  Citations, family size, opposition and the value of patent rights.  _Research Policy_ 32, 1343–1363, https://doi.org/10.1016/S0048-7333(02)00124-5 (2003).
  * [14] Kito, T., Moriya, N. & Yamanoi, J.  Inter-organisational patent opposition network: How companies form adversarial relationships.  _Japanese Economic Review_ 72, 145–166, https://doi.org/10.1007/s42973-020-00057-5 (2021).
  * [15] Perc, M.  The social physics collective.  _Journal of the Korean Physical Society_ 9, 16549, https://doi.org/10.1038/s41598-019-53300-4 (2019).
  * [16] Milo, R. _et al._ Network motifs: Simple building blocks of complex networks.  _Science_ 298, 824–827, https://doi.org/10.1126/science.298.5594.824 (2002).
  * [17] Kovanen, L., Karsai, M., Kaski, K., Kertész, J. & Saramäki, J.  Temporal motifs in time-dependent networks.  _Journal of Statistical Mechanics_ 2011, P11005, https://doi.org/10.1088/1742-5468/2011/11/P11005 (2011).
  * [18] Song, C., Ge, T., Chen, C. & Wang, J.  Event pattern matching over graph streams.  _Proc. of the VLDB Endowment_ 8, 413–424, https://doi.org/10.14778/2735496.2735504 (2014).
  * [19] Hulovatyy, Y., Chen, H. & Milenković, T.  Exploring the structure and function of temporal networks with dynamic graphlets.  _Bioinformatics_ 31, i171–i180, https://doi.org/10.1093/bioinformatics/btv227 (2015).
  * [20] Paranjape, A., Benson, A. R. & Leskovec, J.  Motifs in temporal networks.  In _ACM Conf. on Web Search and Data Mining_ , 601–610, https://doi.org/10.1145/3018661.3018731 (ACM, 2017).
  * [21] Liu, P., Guarrasi, V. & Sarıyüce, A. E.  Temporal network motifs: Models, limitations, evaluation.  _IEEE Trans. Knowledge and Data Engineering (To appear)_ https://doi.org/10.1109/TKDE.2021.3077495 (2021).
  * [22] Holme, P. & Saramäki, J.  Temporal networks.  _Physics Rep._ 519, 97–125, https://doi.org/10.1016/j.physrep.2012.03.001 (2012).
  * [23] Holme, P.  Modern temporal network theory: A colloquium.  _European Physical Journal B_ 88, 234, https://doi.org/10.1140/epjb/e2015-60657-4 (2015).
  * [24] Bajardi, P., Barrat, A., Natale, F., Savini, L. & Colizza, V.  Dynamical patterns of cattle trade movements.  _PLoS ONE_ 6, e19869, https://doi.org/10.1371/journal.pone.0019869 (2011).
  * [25] Jurgens, D. & Lu, T.-C.  Temporal motifs reveal the dynamics of editor interactions in wikipedia.  In _AAAI Conf. on Weblogs and Social Media_ (2012).
  * [26] Kovanen, L., Kaski, K., Kertész, J. & Saramäki, J.  Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences.  _Proc. of the National Academy of Sciences USA_ 110, 18070–18075, https://doi.org/10.1073/pnas.1307941110 (2013).
  * [27] Li, M.-X. _et al._ Statistically validated mobile communication networks: The evolution of motifs in european and chinese data.  _New Journal of Physics_ 16, 083038, https://doi.org/10.1088/1367-2630/16/8/083038 (2014).
  * [28] Zhang, Y.-Q., Li, X., Xu, J. & Vasilakos, A. V.  Human interactive patterns in temporal networks.  _IEEE Trans. Systems, Man, and Cybernetics: Systems_ 45, 214–222, https://doi.org/10.1109/TSMC.2014.2360505 (2015).
  * [29] Masuda, N. & Lambiotte, R.  _A Guide to Temporal Networks, Second Edition_ (World Scientific, Singapore, 2020).
  * [30] Park, Y., Lee, M. J. & Son, S.-W.  Motif dynamics in signed directional complex networks.  _Journal of the Korean Physical Society_ 78, 535–541 (2021).
  * [31] van Dijk, B.  Orbis Database.  https://www.bvdinfo.com/en-gb/our-products/data/international/orbis (2020).  Accessed 10 Jan 2020.
  * [32] van Dijk, B.  Orbis Intellectual Property Database.  https://www.bvdinfo.com/en-us/our-products/data/international/orbis-intellectual-property (2020).  Accessed 10 Jan 2020.
  * [33] Gauvin, L. _et al._ Randomized reference models for temporal networks.  _arXiv preprint arXiv:1806.04032_ (2018).
  * [34] Heider, F.  Attitudes and cognitive organization.  _Journal of Psychology_ 21, 107–112, https://doi.org/10.1080/00223980.1946.9917275 (1946).
  * [35] Cartwright, D. & Harary, F.  Structural balance: A generalization of Heider’s theory.  _Psychological Review_ 63, 277–293, https://doi.org/10.1037/h0046049 (1956).
  * [36] Leskovec, J., Huttenlocher, D. & Kleinberg, J.  Signed networks in social media.  In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , 1361–1370, https://doi.org/10.1145/1753326.1753532 (2010).
  * [37] Artzy-Randrup, Y., Fleishman, S. J., Ben-Tal, N. & Stone, L.  Comment on “Network motifs: Simple building blocks of complex networks” and “Superfamilies of evolved and designed networks”.  _Science_ 305, 1107–1107, https://doi.org/10.1126/science.1099334 (2004).

## Acknowledgements

P.L., N.M., and A.E.S. acknowledges the support by JP Morgan Chase and Company
Faculty Research Award.

## Author contributions statement

N.M., T.K., and A.E.S. conceived the research; N.M., T.K., and A.E.S designed
the research; T.K. collected the data; P.L. and T.K. analyzed the data; P.L.,
N.M., T.K., and A.E.S. discussed the results and wrote the paper.

## Competing interests

The authors declare no competing interests


* [115] K. Horák, B. Bošanský, and M. Pěchouček, “Heuristic search value iteration for one-sided partially observable stochastic games,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , Feb. 2017\.
  * [116] P. Tomášek, B. Bosansky, and T. Nguyen, _Using One-Sided Partially Observable Stochastic Games for Solving Zero-Sum Security Games with Sequential Attacks_ , 12 2020, pp. 385–404.
  * [117] J. Heinrich and D. Silver, “Deep reinforcement learning from self-play in imperfect-information games,” _CoRR_ , vol. abs/1603.01121, 2016.
  * [118] T. H. Nguyen, M. Wright, M. P. Wellman, and S. Singh, “Multistage attack graph security games: Heuristic strategies, with empirical game-theoretic analysis,” _Security and Communication Networks_ , vol. 2018, p. 2864873, Dec 2018.
  * [119] C. Bakker, A. Bhattacharya, S. Chatterjee, and D. L. Vrabie, “Learning and information manipulation: Repeated hypergames for cyber-physical security,” _IEEE Control Systems Letters_ , vol. 4, no. 2, 2020.
  * [120] Z. Wan, J.-H. Cho, M. Zhu, A. H. Anwar, C. A. Kamhoua, and M. P. Singh, “Foureye: Defensive deception against advanced persistent threats via hypergame theory,” _IEEE Transactions on Network and Service Management_ , vol. 19, no. 1, pp. 112–129, 2022.
  * [121] H. Zhang, J. Tan, X. Liu, S. Huang, H. Hu, and Y. Zhang, “Cybersecurity threat assessment integrating qualitative differential and evolutionary games,” _IEEE Transactions on Network and Service Management_ , vol. 19, no. 3, pp. 3425–3437, 2022.
  * [122] H. Hu, Y. Liu, C. Chen, H. Zhang, and Y. Liu, “Optimal decision making approach for cyber security defense using evolutionary game,” _IEEE Transactions on Network and Service Management_ , vol. 17, no. 3, pp. 1683–1700, 2020.
  * [123] K. Durkota, V. Lisy, B. Bošansky, and C. Kiekintveld, “Optimal network security hardening using attack graph games,” in _Proceedings of the 24th International Conference on Artificial Intelligence_ , 2015.
  * [124] K. Horák, B. Bosanský, P. Tomásek, C. Kiekintveld, and C. A. Kamhoua, “Optimizing honeypot strategies against dynamic lateral movement using partially observable stochastic games,” _Comput. Secur._ , vol. 87, 2019.
  * [125] R. Píbil, V. Lisý, C. Kiekintveld, B. Bošanský, and M. Pěchouček, “Game theoretic model of strategic honeypot selection in computer networks,” in _Decision and Game Theory for Security_ , J. Grossklags and J. Walrand, Eds., 2012.
  * [126] O. Tsemogne, Y. Hayel, C. Kamhoua, and G. Deugoue, _Partially Observable Stochastic Games for Cyber Deception Against Network Epidemic_ , 12 2020, pp. 312–325.
  * [127] K. C. Nguyen, T. Alpcan, and T. Basar, “Stochastic games for security in networks with interdependent nodes,” in _2009 International Conference on Game Theory for Networks_ , 2009, pp. 697–703.
  * [128] A. Laszka, W. Abbas, S. S. Sastry, Y. Vorobeychik, and X. Koutsoukos, “Optimal thresholds for intrusion detection systems,” in _Proceedings of the Symposium and Bootcamp on the Science of Security_ , 2016.
  * [129] T. Alpcan and T. Basar, “A game theoretic analysis of intrusion detection in access control systems,” in _2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601)_ , 2004.
  * [130] Q. Zhu and T. Başar, “Dynamic policy-based ids configuration,” in _Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference_ , 2009.
  * [131] A. Aydeger, M. H. Manshaei, M. A. Rahman, and K. Akkaya, “Strategic defense against stealthy link flooding attacks: A signaling game approach,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 1, pp. 751–764, 2021.
  * [132] S. A. Zonouz, H. Khurana, W. H. Sanders, and T. M. Yardley, “Rre: A game-theoretic intrusion response and recovery engine,” in _2009 IEEE/IFIP International Conference on Dependable Systems & Networks_, 2009, pp. 439–448.
  * [133] Khraisat _et al._ , “Survey of intrusion detection systems: techniques, datasets and challenges,” _Cybersecurity_ , vol. 2, no. 1, p. 20, 2019.
  * [134] J. Dromard, G. Roudière, and P. Owezarski, “Online and scalable unsupervised network anomaly detection method,” _IEEE Transactions on Network and Service Management_ , vol. 14, no. 1, pp. 34–47, 2017.
  * [135] A. G. Tartakovsky, B. L. Rozovskii, R. B. Blažek, and H. Kim, “Detection of intrusions in information systems by sequential change-point methods,” _Statistical Methodology_ , vol. 3, no. 3, 2006.
  * [136] C. J. Fung, J. Zhang, and R. Boutaba, “Effective acquaintance management based on bayesian learning for distributed intrusion detection networks,” _IEEE Transactions on Network and Service Management_ , vol. 9, no. 3, pp. 320–332, 2012.
  * [137] P. Holgado, V. A. Villagrá, and L. Vázquez, “Real-time multistep attack prediction based on hidden markov models,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 17, no. 1, pp. 134–147, 2020.
  * [138] S. Huang _et al._ , “Hitanomaly: Hierarchical transformers for anomaly detection in system log,” _IEEE Transactions on Network and Service Management_ , vol. 17, no. 4, pp. 2064–2076, 2020.
  * [139] I. Siniosoglou, P. Radoglou-Grammatikis, G. Efstathopoulos, P. Fouliras, and P. Sarigiannidis, “A unified deep learning anomaly detection and classification approach for smart grid environments,” _IEEE Transactions on Network and Service Management_ , vol. 18, no. 2, 2021.
  * [140] D. Anderson, T. Frivold, and A. Valdes, “Next-generation intrusion detection expert system (nides) a summary,” 01 1995.
  * [141] R. Heenan and N. Moradpoor, “Introduction to security onion,” in _The First Post Graduate Cyber Security Symposium_ , 2016.
  * [142] V. Paxson, “Bro: a system for detecting network intruders in real-time,” _Computer networks_ , vol. 31, no. 23-24, pp. 2435–2463, 1999.
  * [143] S. Lewandowski, D. Van Hook, G. O’Leary, J. Haines, and L. Rossey, “Sara: Survivable autonomic response architecture,” in _Proceedings DARPA Information Survivability Conference and Exposition II. DISCEX’01_ , vol. 1, 2001, pp. 77–88 vol.1.
  * [144] B. Foo, Y.-C. Mao, and E. Spafford, “Adepts: Adaptive intrusion response using attack graphs in an e-commerce environment,” in _Proceedings of the 2005 International Conference on Dependable Systems and Networks_ , ser. DSN ’05, USA, 2005, p. 508–517.
  * [145] A. Uprety and D. B. Rawat, “Reinforcement learning for iot security: A comprehensive survey,” _IEEE Internet of Things Journal_ , vol. 8, no. 11, pp. 8693–8706, 2021.
  * [146] S. ”Jajodia, G. Cybenko, P. Liu, C. Wang, and M. Wellman, _Adversarial and Uncertain Reasoning for Adaptive Cyber Defense: Control- and Game-Theoretic Approaches to Cyber Security_. Cham: Springer International Publishing, 2019.
  * [147] J. L. Hellerstein, Y. Diao, S. Parekh, and D. M. Tilbury, _Feedback Control of Computing Systems_. USA: Wiley & Sons, 2004.
  * [148] M. Tambe, _Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned_ , 1st ed. USA: Cambridge University Press, 2011.
  * [149] C. J. Fung and R. Boutaba, _Intrusion Detection Networks - A Key to Collaborative Security_. CRC Press, 2013\.
  * [150] L. Buttyan and J.-P. Hubaux, _Security and Cooperation in Wireless Networks: Thwarting Malicious and Selfish Behavior in the Age of Ubiquitous Computing_. USA: Cambridge University Press, 2007.
  * [151] J. Collyer, A. Andrew, and D. Hodges, “Acd-g: Enhancing autonomous cyber defense agent generalization through graph embedded network representation,” in _Proceedings of the ML4Cyber workshop, ICML 2022, Baltimore, USA, July 17-23, 2022_. PMLR, 2022.
  * [152] S. G. Aksoy, E. Purvine, and S. J. Young, “Directional laplacian centrality for cyber situational awareness,” _Digital Threats_ , oct 2021.
  * [153] J. Wang, C. Song, and H. Yin, “Reinforcement learning-based hierarchical seed scheduling for greybox fuzzing,” in _NDSS_ , 2021.
  * [154] T. Avgerinos, D. Brumley, J. Davis, R. Goulden, T. Nighswander, A. Rebert, and N. Williamson, “The mayhem cyber reasoning system,” _IEEE Security Privacy_ , vol. 16, no. 2, pp. 52–60, March 2018.
  * [155] A. N. Kulkarni and J. Fu, “A theory of hypergames on graphs for synthesizing dynamic cyber defense with deception,” 2020.
  * [156] N. Dhir, H. Hoeltgebaum, N. Adams, M. Briers, A. Burke, and P. Jones, “Prospective artificial intelligence approaches for active cyber defence,” _CoRR_ , vol. abs/2104.09981, 2021, https://arxiv.org/abs/2104.09981.
  * [157] J. A. Emanuello and A. Ridley, “The mathematics of cyber defense,” 2022, notices of the American Mathematical Society (AMS).
  * [158] E. Al-Shaer, J. Wei, K. W. Hamlen, and C. Wang, _Autonomous Cyber Deception - Reasoning, Adaptive Planning, and Evaluation of HoneyThings_. Springer, 2019.
  * [159] K. Han, J. H. Choi, Y. Choi, G. M. Lee, and A. B. Whinston, “Security defense against long-term and stealthy cyberattacks,” _Decision Support Systems_ , p. 113912, 2022.
  * [160] O. Vaněk, Z. Yin, M. Jain, B. Bošanský, M. Tambe, and M. Pěchouček, “Game-theoretic resource allocation for malicious packet detection in computer networks,” in _Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems_ , 2012.
  * [161] J. Brynielsson and S. Arnborg, “Bayesian games for threat prediction and situation analysis,” in _Proceedings of the 7th International Conference on Information Fusion_ , vol. 2, Stockholm, Jun. 2004.
  * [162] U. Franke and J. Brynielsson, “Cyber situational awareness - a systematic review of the literature,” _Comput. Secur._ , vol. 46, 2014.
  * [163] S. Sengupta and S. Kambhampati, “Multi-agent reinforcement learning in bayesian stackelberg markov games for adaptive moving target defense,” _CoRR_ , vol. abs/2007.10457, 2020.
  * [164] M. Alario-Nazaret, J. P. Lepeltier, and B. Marchal, “Dynkin games,” in _Stochastic Differential Systems_ , M. Kohlmann and N. Christopeit, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1982, pp. 23–32.
  * [165] E. Solan and N. Vieille, “Deterministic multi-player dynkin games,” 2002.
  * [166] J. Lempa and P. Matomäki, “A dynkin game with asymmetric information,” 2010.
  * [167] E. Ekström, K. Glover, and M. Leniec, “Dynkin games with heterogeneous beliefs,” _Journal of Applied Probability_ , no. 1, 2017.
  * [168] T. Noe, “Capital structure and signaling game equilibria,” _Review of Financial Studies_ , vol. 1, no. 4, pp. 331–355, 1988.
  * [169] M. H. Manshaei, Q. Zhu, T. Alpcan, T. Basar, and J.-P. Hubaux, “Game theory meets network security and privacy,” _ACM Comput. Surv._ , vol. 45, no. 3, pp. 25:1–25:39, Jul. 2013.
  * [170] B. Lantz, B. Heller, and N. McKeown, “A network in a laptop: Rapid prototyping for software-defined networks,” in _Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks_ , 2010.
  * [171] A. Teixeira, S. Amin, H. Sandberg, K. H. Johansson, and S. S. Sastry, “Cyber security analysis of state estimators in electric power systems,” in _49th IEEE Conference on Decision and Control (CDC)_ , 2010.
  * [172] A. Teixeira, K. C. Sou, H. Sandberg, and K. H. Johansson, “Secure control systems: A quantitative risk management approach,” _IEEE Control Systems Magazine_ , vol. 35, no. 1, pp. 24–45, 2015.
  * [173] H. Sandberg, S. Amin, and K. H. Johansson, “Cyberphysical security in networked control systems: An introduction to the issue,” _IEEE Control Systems Magazine_ , vol. 35, no. 1, pp. 20–23, 2015.
  * [174] M. S. Chong, H. Sandberg, and A. M. Teixeira, “A tutorial introduction to security and privacy for cyber-physical systems,” in _2019 18th European Control Conference (ECC)_ , 2019, pp. 968–978.
  * [175] A. Leva, M. Maggio, A. V. Papadopoulos, and F. Terraneo, _Control-Based Operating System Design_. Institution of Engineering and Technology, 2013.
  * [176] M. Rasouli, E. Miehling, and D. Teneketzis, “A scalable decomposition method for the dynamic defense of cyber networks,” in _Game Theory for Security and Risk Management: From Theory to Practice_ , 2018.
  * [177] ——, “A supervisory control approach to dynamic cyber-security,” in _Decision and Game Theory for Security_ , 2014.
  * [178] E. Miehling, M. Rasouli, and D. Teneketzis, “Optimal defense policies for partially observable spreading processes on bayesian attack graphs,” in _Proceedings of the 2nd ACM Workshop on Moving Target Defense_ , ser. MTD ’15, New York, 2015, p. 67–76.
  * [179] R. Bellman, _Dynamic Programming_. Dover Publications, 1957.
  * [180] D. P. Bertsekas and J. N. Tsitsiklis, _Neuro-dynamic programming._ Belmont, MA: Athena Scientific, 1996.
  * [181] D. Silver _et al._ , “Mastering the game of Go with deep neural networks and tree search,” _Nature_ , vol. 529, no. 7587, pp. 484–489, Jan. 2016\.
  * [182] C. Berner _et al._ , “Dota 2 with large scale deep reinforcement learning,” _ArXiv_ , vol. abs/1912.06680, 2019.
  * [183] M. Standen, M. Lucas, D. Bowman, T. J. Richer, J. Kim, and D. Marriott, “Cyborg: A gym for the development of autonomous cyber agents,” _CoRR_ , https://arxiv.org/abs/2108.09118.
  * [184] L. Li, R. Fayad, and A. Taylor, “Cygil: A cyber gym for training autonomous agents over emulated network systems,” _CoRR_ , vol. abs/2109.03331, 2021\.
  * [185] A. Molina-Markham, C. Miniter, B. Powell, and A. Ridley, “Network environment design for autonomous cyberdefense,” 2021, https://arxiv.org/abs/2103.07583.
  * [186] D. Bertsekas, _Rollout, Policy Iteration, and Distributed Reinforcement Learning_ , ser. Athena scientific optimization and computation series. Athena Scientific., 2021.

|  Kim Hammar Kim Hammar is currently pursuing the Ph.D. degree at the
Division of Network and Systems Engineering at KTH Royal Institute of
Technology in Stockholm, Sweden. Before starting his Ph.D., he received the
B.Sc. and M.Sc. degree in computer engineering with a specialization in
distributed systems from KTH Royal Institute of Technology in 2016 and 2018,
respectively. His research interests are in the intersection between decision
theory, machine learning, and large-scale systems, focusing on cybersecurity
applications.
---|---
|  Rolf Stadler Rolf Stadler is a professor at KTH Royal Institute of
Technology in Stockholm, Sweden, and head of the Division of Network and
Systems Engineering. He holds an M.Sc. degree in mathematics and a Ph.D. in
computer science from the University of Zurich. Before joining KTH in 2001, he
held positions at the IBM Zurich Research Laboratory, Columbia University, and
ETH Zürich. His group made contributions to real-time monitoring, resource
management, and automation for large-scale networked systems. His current
interests include data-driven methods for network engineering and management,
as well as AI techniques for cybersecurity. Rolf Stadler has been Editor-in-
Chief of IEEE Transactions on Network and Service Management (TNSM) 2014-2017.
---|---