Simulating Spreading of Multiple Interacting Processes in Complex Networks 1stMichał Czuba

2025-04-26 0 0 779.51KB 10 页 10玖币

侵权投诉

Simulating Spreading of Multiple Interacting

Processes in Complex Networks

1st Michał Czuba

Department of Artiﬁcial Intelligence

Wrocław University of Science and Technology

Wrocław, Poland

michal.czuba@pwr.edu.pl

2nd Piotr Bródka

Department of Artiﬁcial Intelligence

Wrocław University of Science and Technology

Wrocław, Poland

piotr.brodka@pwr.edu.pl

Abstract—Investigating the interaction between spreading pro-

cesses in complex networks is one of the most important chal-

lenges in network science. However, whether we would like to

know how the information campaign will affect virus spreading

or how the advertising campaign of the new iPhone will affect the

sales of Samsung phones, we need an environment that will allow

us to evaluate under what conditions our spreading campaign

will be effective. Network Diffusion is a Python package that

should help do that. In this paper, we introduce its operating

principle and main functionalities, including simple examples of

simulations that can be performed using it.

Index Terms—interacting spreading processes, epidemics, net-

work science, multilayer network

I. INTRODUCTION

For almost two years now, the resources of the entire world

have been used for the ﬁght against the "invisible" enemy.

We spent countless hours and trillions of dollars to stop the

COVID-19 pandemic, and still, millions of people have died

from the virus or the collapse of healthcare systems around

the world. One of the challenging tasks is understanding how

different countermeasures, such as information campaigns,

lockdowns, or vaccinations, affect the progression of the virus

to choose those that will save both human lives and the

economy.

In this paper, we would like to present the Network Diffusion

package [1]that allows simulating the spread of many coexist-

ing processes in single and multilayer networks. An example

of such processes would be, of course, coronavirus spread,

interacting with an information campaign and vaccinations,

but also the interaction between two advertising campaigns

(e.g. iPhone vs Samsung or Cannon vs Nikon), two political

campaigns (e.g. Biden vs Trump), diseases (e.g., AIDS and

Tuberculosis), to name just a few [2]. However, before we

can present the Network Diffusion package, we would like to

introduce a few key concepts from network science [3].

A. Complex networks

Complex networks are the backbone of all complex sys-

tems [3] starting from the nervous system of living organ-

isms [4], through our infrastructure systems (electric grid, wa-

ter pipes, airports, etc.) [5], [6], and ending with relationships

This work was partially supported by the Polish National Science Centre,

under Grant no. 2016/21/D/ST6/02408

between people [7]. Complex networks can be represented

and analysed in multiple ways, e.g., adjacency matrix [3] or

property vectors [8], however, the most common approach is to

represent a complex network as a graph [3] or a set of graphs

(for multilayer networks) [9], [10]. The multilayer network,

according to [9], is deﬁned as quadruple M= (N, L, V, E);

where: Nis a set of actors; Lis a set of layers; Vis a set of

nodes, V⊆N×L;Eis a set of edges (v1, v2) : v1, v2∈V,

and if v1= (n1, l1)and v2= (n2, l2)∈Ethen l1=l2.

B. Spreading phenomena

Spreading phenomenon covers a wide spectrum of pro-

cesses, starting from information diffusion [11], through

virus [12], opinion [13], innovation [14] spreading and end-

ing with the spread of inﬂuence [15]. Fortunately, all these

processes are similar if we look at their high-level compo-

nents [3] (i) What phenomenon is spreading (e.g. information,

opinion, virus), (ii) How/Who it is spreading (e.g. network

nodes, actors, agents), and (iii) Where it is spreading (i.e.

network type). All these elements carry a different context

to the simulation results, but, at the same time, they can be

imagined as "containers" for algorithmic structures, which will

be introduced later. An example of those three components

can be a viral video that spreads on a social networking site.

Here, what is the video or digital content, how/who is a link

to the website or a post on social media, and where is a

social network that is the foundation of this particular social

networking site.

1) Epidemic modelling framework: The initial models

developed by epidemiologists are based on two assump-

tions [3]: compartmentalisation and homogeneous mixing.

The ﬁrst condition says that the state of each individual is

discrete. This means (continuing with epidemiological analo-

gies) that the relation of a given node to a disease can

be described by nstates, e.g. healthy,sick. The second

assumption concerns the ability of the nodes to change

their states. Each individual can interact with all nodes in

a given time unit. Using that hypothesis, we can build

many various spreading models like SI (Suspected-Infected),

SIS (Suspected-Infected-Suspected), SIR (Suspected-Infected-

Recovered), SIRS (Suspected-Infected-Recovered-Suspected),

and so on. Epidemic models can be used to simulate other

arXiv:2210.06010v1 [cs.SI] 12 Oct 2022

spreading processes. The most common example would be

information spreading, where we have models like UAU [16]

(Unaware-Aware-Unaware) or UAF [17] (Unaware-Aware-

Forgot), which are based on SIS and SIR models, respectively.

2) Independent cascade model: Independent cascade model

(ICM) [15] has a much different mechanism and is widely

used to simulate inﬂuence diffusion. Its principles reject the

homogeneous mixing assumption because of the way the

phenomenon propagates - it cannot be captured holistically

for a given network. Here, the spreading takes the form of a

cascade. Each newly activated node has one chance to activate

its neighbours in each step. It is based on the likelihood of

activation (aka. propagation probability) stored at the edge

connecting them [18].

3) Linear threshold model: This model is based on the

concept of the activation threshold that is deﬁned for each node

of the network [15]. It determines a minimum value of the

inﬂuence of its neighbours to change its state. In other words,

the minimum value above must be the sum of the intensity

of the connections from the neighbouring activated nodes to

result in activation [18]. When comparing ICM and Linear

Threshold Model (LTM), one can say that the ﬁrst one is based

on the push mechanism, i.e., a node pushes its inﬂuence to its

neighbours. In contrast, LTM is based on the pull mechanism,

i.e. the node pulls the inﬂuence from its neighbours.

C. Interacting spreading processes in networks

When analysing how various phenomena in networks prop-

agate, we have to ask the following questions: what is being

propagated? and where is it being propagated?. As an answer,

we get four general possibilities: (1) a single process in a

single network, (2) a single process in a multilayer network,

(3) multiple processes in a single network, and (4) multiple

processes in a multilayer network.

The last two options bring the possibility of spreading

multiple processes that can interact with each other. Thus,

in addition to modelling each phenomenon, we also need to

model the interactions between them, i.e., how they inﬂuence

each other (and that is exactly a problem that Network Dif-

fusion solves). Below, we brieﬂy describe the four possible

variants of interactions.

Firstly, we can distinguish supporting processes (about 11%

of research in the domain [2]) that mutually support each other

by increasing coverage and velocity. Here, a good illustration

is that chronic diseases (such as asthma) are a catalyst for

contracting COVID-19.

The next genres are competing processes (about 36% pub-

lications [2]). In this case, one process causes suppression of

the propagation of the other. A good example of this is the

presidential election: if the number of people inﬂuenced by

candidate X increases, the number of people inﬂuenced by

candidate Y has to decrease, and at the end of the day, only

one candidate can win.

The third case, the mixed approach, covers about 46% of

the publications [2]. It considers instances where one process

supports the second, but the second competes with the ﬁrst.

An interaction between disease and awareness can be a good

example. People who get sick become aware of a disease,

so the more people get sick, the more people will be aware.

On the other hand, people aware of the pandemic will take

preventive actions to limit its spreading.

The last case is when processes do not interact with each

other. It appears only in 7% of the papers in the domain [2].

II. SIMILAR SOFTWARE PACKAGES

To gain valuable recognition of similar solutions to Net-

work Diffusion, an appropriate tool review methodology was

adopted. For this, the general state of the software available

in the ﬁeld was taken into account. We started from a simple

reconnaissance using a search engine and focused more on the

tools available for the Python language; however, it was not

a strict condition. Our ﬁnal goal was to see a general cross-

section of state-of-the-art. As a result, information on more

than twenty different tools was obtained. We analysed them

and divided them into two groups: packages dedicated for

network spreading simulations and general complex network

analysis software.

A. Software for spreading processes simulations

1) GLEaMviz: The ﬁrst application that has functionali-

ties corresponding to the designed software is a GLEaMviz.

It works with real data, population density, and migration

around the world, combined with stochastic models of disease

propagation. As a result, it provides a sophisticated simulation

environment. Due to the large scale of the experiments (the

whole world), a single node is a population of a given size

(deﬁned by the user). A very interesting feature is the manual

deﬁnition of the epidemiological model. GLEaMviz makes

this possible by manipulating the compartments (understood in

the same way as in sec. I-B1). Allowable transitions between

them are also fully deﬁnable. The user can also select the

geographical start of the disease, the initial percentages of

individuals belonging to a given compartment, its duration, etc.

There is also an option to generate various visualisations at the

end of the experiment. Despite the interesting functionalities

mentioned above, GLEaMviz has a rather large disadvantage:

it only allows the propagation of one process at a time [19].

2) NDLIB: Network Diffusion LIBrary is a Python package

based on the NetworkX library. It allows performing simula-

tions with many predeﬁned epidemiological models (such as:

SIS, SIR, SEIR, etc.), inﬂuence group (LTM, ICM, Proﬁle,

etc.), opinion group (Voter, Sznajd, etc.), and even dynamics

(models with the capacity to change the topology of network).

Moreover, the user can create its own customised models.

Results visualisation is also possible via Matplotlib or Bokeh

with the ﬂexibility to append a custom graphical engine.

NDLIB also has some interesting run-time features. First

of all, it includes an option to perform a "multi-execution"

of the simulation by parallel computing. As this kind of

experiment is generally stochastic, this feature gives a chance

to see the general behaviour of the observed phenomena.

It also enables running the simulation on a server (as well

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SimulatingSpreadingofMultipleInteractingProcessesinComplexNetworks1stMichaCzubaDepartmentofArticialIntelligenceWrocawUniversityofScienceandTechnologyWrocaw,Polandmichal.czuba@pwr.edu.pl2ndPiotrBródkaDepartmentofArticialIntelligenceWrocawUniversityofScienceandTechnologyWrocaw,Polandpiotr.brodk...

展开>> 收起<<

Simulating Spreading of Multiple Interacting Processes in Complex Networks 1stMichał Czuba.pdf

共10页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Simulating Spreading of Multiple Interacting Processes in Complex Networks 1stMichał Czuba

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: