current position:Home>[Python homework] coupling network information dissemination

[Python homework] coupling network information dissemination

2022-01-29 13:02:55 Dream chaser


Preface

Tell the truth , I haven't written a blog for a long time , The last blog post was two months ago . But in this case , Fans are going up ,hh, This is true, which I didn't expect , It really makes me feel guilty .
Of course, I haven't written a blog lately , Except that I can't find a suitable subject , The most important thing is that I've been a little busy recently ( attend class;class begins 、 Experimental report 、 Bodybuilding 、 Do the project 、 The meeting …) The rest of the time is scattered , There's no way to calm down and write .

This time, I mainly took advantage of the need to write an experimental report , So I easily rewrite the idea of the experimental report into a blog , And the homework topic is also very interesting , It is coupling network information dissemination , It can simulate the spread of virus or information , Listen, do you have a feeling of being tall ? So I wrote it into a blog for your study and reference .( Another piece of water ~)

notes : The code of this blog is only for learning and communication , No plagiarism !


One 、 Topic introduction

The title of the assignment is PPT file , It's a headline
 Insert picture description here
The second page is the idea of solving the problem ( To tell you the truth, it's a little abrupt , I didn't even know what the problem was, so I began to ask me to do it step by step , It's true. I'm a little confused , It's better to add a specific question here , For example, use Python Write a program to simulate the information transmission of the coupling network )
 Insert picture description here
 Insert picture description here
 Insert picture description here
 Insert picture description here
 Insert picture description here
 Insert picture description here

 Insert picture description here
 Insert picture description here

 Insert picture description here
The above is the topic of PPT Content .

Two 、 Their thinking

The content of the topic is to write a program to simulate the information transmission of the coupling network .

Their thinking PPT The document has actually told us , We just need to follow PPT The code can be reproduced step by step .

1. Construct a coupling network

according to PPT It means , It should be for us to construct a ER-BA Two layer network .
 Insert picture description here

① structure ER The Internet

Generate ER Random network ( Algorithm ):
initial : Network summary points N, There is no side ;
Network construction process : Each pair of nodes in probability p Selected , Connect the edges , Repeated edge connection is not allowed .

I use adjacency matrix here ( about Python It's a two-dimensional list ) To the storage network ,ER[i][j]==1 Just explain i and j There are connections between nodes , On the contrary, there is no connection . Here we use a global two-dimensional array variable ER To store .

According to the generation rules, we write the following code to generate ER Random network ( Note the encapsulation of the method here , Put these variable probabilities 、 The number of nodes is taken as the input parameter , So that the parameters can be changed later ), Here we use random.random() Method to simulate probability , When the randomly generated number is less than the probability, the edge is generated .

# ER Random network 
ER = [[]]
#  Generate ER Random network ,n Indicates the number of points ,p Represents the probability of generating edges 
def generateER(n, p):
    global ER
    #  This statement can avoid shallow copy problems 
    ER = [([0] * n) for i in range(n)]
    for i in range(0, n):
        for j in range(i + 1, n):
            #  Randomly generated number 
            x = random.random()
            #  Probability generation edge 
            if x < p:
                ER[i][j] = 1
                ER[j][i] = 1

② structure BA The Internet

BA Scale free network

(1) Initially, the network has m_0 Nodes , There can be no side , It can also be like ER Generate some edges like a network ; Or before m_0 A node is a fully connected structure . (2)
Every time step , A new node joins the network , And select... From existing networks m Nodes (m≤m_0) Connected to it , Choice probability p_i With existing nodes i In direct proportion to the degree of p_i=k_i/∑_j▒k_j

(3) When there is N After nodes , stop it .

Again BA Scale free networks are also stored in adjacency matrix , Here, code according to the given rules .
Considering the complexity of the rules , It can be divided into the following steps :

  • initialization BA The Internet , here BA The Internet only has m0 Initial nodes , The side relationship is arbitrary
  • Iterative increase m Nodes , Every time a node is added, it will find according to the rule probability m Nodes

The above logic implementation is somewhat complex , Here we simplify the conditions to achieve the effect required by the topic :

  • It is assumed that each time a node is added, at least m A degree is not 0 The node of ( Because if there is no m A degree is not 0 The node of , This means that we need to consider the degree of 0 The situation of )
  • initial m0 The network composed of nodes is a fully connected network

Because... Is selected every time you add nodes m The operation of two nodes is too complex , So I encapsulate it as a way to increase code readability .

Here is the code implementation :

# BA Scale free network 
BA = [[]]
#  In subscript 0 To end Of klist The list is based on k Weight to find a subscript to return , barring exclude_list The nodes in the 
def findOne(klist, end, exclude_list):
    flag = True
    k_sum = 0
    for i in range(0, end):
        k_sum += klist[i]
    result = end - 1
    while flag:
        x = random.random() * k_sum
        pre = 0
        for i in range(0, end):
            pre += klist[i]
            if pre > x:
                result = i
                break
        flag = False
        #  Check whether the result is in exclude_list in , If so, start again , Otherwise, the result 
        for i in exclude_list:
            if i == result:
                flag = True
                break
    return result


#  according to BA The rules of scale-free networks are klist( Subscript to be 0 To end  Between ) Search for m Number 
#  To simplify logic , Compete here (k!=0) The number of nodes must be greater than m
def find(k_list, m, end):
    #  Result array 
    result = []
    #  initialization 
    for i in range(0, m):
        j = findOne(k_list, end, result)
        #  Increase results 
        result.append(j)
    return result


#  Generate BA Scale free network ,n Indicates the number of points ,m0 Indicates the number of initial nodes 
def generateBA(n, m0, m):
    global BA
    #  initial BA Scale free network ( Use the generator to create and avoid shallow copies )
    BA = [([0] * n) for i in range(n)]
    #  Before initialization m0 All nodes are connected networks 
    for i in range(0, m0):
        for j in range(i + 1, m0):
            BA[i][j] = 1
            BA[j][i] = 1
    #  Initial degree array 
    k_list = [m0 - 1] * m0 + [0] * (n - m)
    #  Traverse the following nodes , Simulation join 
    for i in range(m0, n):
        #  elect m Nodes 
        nodes = find(k_list, m, i)
        for j in nodes:
            BA[i][j] = 1
            BA[j][i] = 1
            #  Update degree array 
            k_list[i] += 1
            k_list[j] += 1

③ double ER-BA A network model

Build a two-tier network structure ( Such as ER-ER network card ,ER-BA The Internet ,BA-BA The Internet ), Suppose that the nodes between layers are connected one-to-one , As shown in the figure below . It is understandable that different social platforms are coupled with each other .

 Insert picture description here
No code operation is required here , But we need to understand ,ER Nodes and BA Nodes are one-to-one , As shown above .
In the code, it can be understood as ER The subscript in the network is i And BA The subscript in the network is i The nodes are actually connected .

2. utilize SIR Model to simulate information dissemination

SIR (Susceptible – Infected - Recoved) model:
 Insert picture description here
SIR Communication model ideas :

If one S ( Healthy or not receiving information ) Status node With a I ( Infection or information disseminator ) State node contact , So this S The probability of a node in a state being infected is β .
therefore , stay t moment , If S The status node has m individual I Status neighbors , So the next time step t + 1, The probability of the node being infected is 1−(1−β)^m.

t Every moment I The status node is in the next time step , namely t + 1 The probability of recovery is γ.

We can translate the above ideas into the following steps :
1. The initial point of infection
2. Iteration loop t Simulation time step , Every iteration , Each node will refresh the status according to the rules

  • If the node status is S( normal , Not infected ), Then it has 1−(1−β)^m The probability of being infected into I state
  • If the node status is I( infected ), Then it has γ The probability of recovery is transformed into R state
  • If the node status is R, Then the state will not change ( Simulate virus immunity )

3. Record... At each point in time S Number of nodes 、I Number of nodes 、R Number of nodes

What we need to pay attention to here is , When considering the surrounding infected nodes , Don't forget to think about ER-BA The Internet “ Upper and lower layers ” Your infection , Because here ER The Internet and BA The nodes corresponding to the network are connected .

When writing code here, we should also consider the input parameters , At the same time, the complex logic is encapsulated to achieve good code readability , Here is the code implementation :

# ER Network infection ,S Expressed as healthy ,I Indicates that it has been infected ,R Indicates recovery 
ER_SIR = []

BA_SIR = []

#  An array used to record daily data 
slist = []
ilist = []
rlist = []
#  Yes ER Online i Node processing ,i Indicates the node subscript ,t Days ,b Indicates the infection coefficient ,y Indicates the rehabilitation coefficient 
def er_sir_one(i, t, b, y):
    global ER, BA, ER_SIR, BA_SIR, slist, ilist, rlist
    if ER_SIR[i] == 'S':
        #  Start counting the number of infected nodes around 
        inum = 0
        for x in range(len(ER_SIR)):
            if (not x == i) and ER[i][x] == 1 and ER_SIR[x] == 'I':
                inum += 1
        #  Because it's a two-tier network , therefore BA Consider also 
        if BA_SIR[i] == 'I':
            inum += 1
            ilist[t] += 1
        p = random.random()
        #  Yes 1-(1-b)^inum Probability of infection 
        if p < 1 - (1 - b) ** inum:
            ER_SIR[i] = 'I'
            ilist[t] += 1
            return
        slist[t] += 1
    elif ER_SIR[i] == 'I':
        p = random.random()
        #  Yes y The chance of recovery 
        if p < y:
            ER_SIR[i] = 'R'
            rlist[t] += 1
            return
        ilist[t] += 1
    else:
        rlist[t] += 1


#  Yes BA Online i Node processing ,i Indicates the node subscript ,t Days ,b Indicates the infection coefficient ,y Indicates the rehabilitation coefficient 
def ba_sir_one(i, t, b, y):
    global ER, BA, ER_SIR, BA_SIR, slist, ilist, rlist
    if BA_SIR[i] == 'S':
        #  Start counting the number of infected nodes around 
        inum = 0
        for x in range(len(BA_SIR)):
            if (not x == i) and BA[i][x] == 1 and BA_SIR[x] == 'I':
                inum += 1

        #  Because it's a two-tier network , therefore ER Consider also 
        if ER_SIR[i] == 'I':
            inum += 1
        p = random.random()
        #  Yes 1-(1-b)^inum Probability of infection 
        if p < 1 - (1 - b) ** inum:
            BA_SIR[i] = 'I'
            ilist[t] += 1
            return
        slist[t] += 1
    #  Yes y The chance of recovery 
    elif BA_SIR[i] == 'I':
        p = random.random()
        if p < y:
            BA_SIR[i] = 'R'
            rlist[t] += 1
            return
        ilist[t] += 1
    else:
        rlist[t]+=1

def sir(b, y, t):
    global ER_SIR, BA_SIR, slist, ilist, rlist
    n = len(ER[0])
    #  initialization ER_SIR,BA_SIR
    ER_SIR = ['S'] * n
    BA_SIR = ['S'] * n

    #  Initialize the array of daily statistics 
    slist = [0] * t
    ilist = [0] * t
    rlist = [0] * t

    #  Random infection ER A node in the network 
    x = random.randint(0, n - 1)
    ER_SIR[x] = 'I'

    #  Traverse t God , Simulated t God 
    for day in range(t):
        #  Traverse all nodes 
        for node in range(n):
            #  Refresh the double-layer network status once 
            er_sir_one(node, day, b, y)
            ba_sir_one(node, day, b, y)

3. drawing

Finally, the results are visualized in the form of charts according to the requirements , This is used here. matplotlib This package , Here is the code implementation :

#  drawing 
plt.plot(list(range(t)), slist, linewidth=4,label=u'S')
plt.plot(list(range(t)), ilist, linewidth=4,label=u'I')
plt.plot(list(range(t)), rlist, linewidth=4,label=u'R')
plt.legend()  #  Let the legend work 
plt.xlabel(u"t")  # X Axis labels 
plt.ylabel("N(t)")  # Y Axis labels 
plt.title("SIR model result")  #  title 
plt.show()

3、 ... and 、 Complete code

The following is the complete code implementation :

import random
import matplotlib.pyplot as plt

# ER Random network 
ER = [[]],
# BA Scale free network 
BA = [[]]

# ER Network infection ,S Expressed as healthy ,I Indicates that it has been infected ,R Indicates recovery 
ER_SIR = []

BA_SIR = []

#  An array used to record daily data 
slist = []
ilist = []
rlist = []


#  Generate ER Random network ,n Indicates the number of points ,p Represents the probability of generating edges 
def generateER(n, p):
    global ER
    #  Avoid shallow copies 
    ER = [([0] * n) for i in range(n)]
    for i in range(0, n):
        for j in range(i + 1, n):
            #  Randomly generated number 
            x = random.random()
            #  Probability generation edge 
            if x < p:
                ER[i][j] = 1
                ER[j][i] = 1


#  In subscript 0 To end Of klist The list is based on k Weight to find a subscript to return , barring exclude_list The nodes in the 
def findOne(klist, end, exclude_list):
    flag = True
    k_sum = 0
    for i in range(0, end):
        k_sum += klist[i]
    result = end - 1
    while flag:
        x = random.random() * k_sum
        pre = 0
        for i in range(0, end):
            pre += klist[i]
            if pre > x:
                result = i
                break
        flag = False
        #  Check whether the result is in exclude_list in , If so, start again , Otherwise, the result 
        for i in exclude_list:
            if i == result:
                flag = True
                break
    return result


#  according to BA The rules of scale-free networks are klist( Subscript to be 0 To end  Between ) Search for m Number 
#  To simplify logic , Compete here (k!=0) The number of nodes must be greater than m
def find(k_list, m, end):
    #  Result array 
    result = []
    #  initialization 
    for i in range(0, m):
        j = findOne(k_list, end, result)
        #  Increase results 
        result.append(j)
    return result


#  Generate BA Scale free network ,n Indicates the number of points ,m0 Indicates the number of initial nodes 
def generateBA(n, m0, m):
    global BA
    #  initial BA Scale free network ( Use the generator to create and avoid shallow copies )
    BA = [([0] * n) for i in range(n)]
    #  Before initialization m0 All nodes are connected networks 
    for i in range(0, m0):
        for j in range(i + 1, m0):
            BA[i][j] = 1
            BA[j][i] = 1
    #  Initial degree array 
    k_list = [m0 - 1] * m0 + [0] * (n - m)
    #  Traverse the following nodes , Simulation join 
    for i in range(m0, n):
        #  elect m Nodes 
        nodes = find(k_list, m, i)
        for j in nodes:
            BA[i][j] = 1
            BA[j][i] = 1
            #  Update degree array 
            k_list[i] += 1
            k_list[j] += 1


#  Yes ER Online i Node processing ,i Indicates the node subscript ,t Days ,b Indicates the infection coefficient ,y Indicates the rehabilitation coefficient 
def er_sir_one(i, t, b, y):
    global ER, BA, ER_SIR, BA_SIR, slist, ilist, rlist
    if ER_SIR[i] == 'S':
        #  Start counting the number of infected nodes around 
        inum = 0
        for x in range(len(ER_SIR)):
            if (not x == i) and ER[i][x] == 1 and ER_SIR[x] == 'I':
                inum += 1
        #  Because it's a two-tier network , therefore BA Consider also 
        if BA_SIR[i] == 'I':
            inum += 1
            ilist[t] += 1
        p = random.random()
        #  Yes 1-(1-b)^inum Probability of infection 
        if p < 1 - (1 - b) ** inum:
            ER_SIR[i] = 'I'
            ilist[t] += 1
            return
        slist[t] += 1
    elif ER_SIR[i] == 'I':
        p = random.random()
        #  Yes y The chance of recovery 
        if p < y:
            ER_SIR[i] = 'R'
            rlist[t] += 1
            return
        ilist[t] += 1
    else:
        rlist[t] += 1


#  Yes BA Online i Node processing ,i Indicates the node subscript ,t Days ,b Indicates the infection coefficient ,y Indicates the rehabilitation coefficient 
def ba_sir_one(i, t, b, y):
    global ER, BA, ER_SIR, BA_SIR, slist, ilist, rlist
    if BA_SIR[i] == 'S':
        #  Start counting the number of infected nodes around 
        inum = 0
        for x in range(len(BA_SIR)):
            if (not x == i) and BA[i][x] == 1 and BA_SIR[x] == 'I':
                inum += 1

        #  Because it's a two-tier network , therefore ER Consider also 
        if ER_SIR[i] == 'I':
            inum += 1
        p = random.random()
        #  Yes 1-(1-b)^inum Probability of infection 
        if p < 1 - (1 - b) ** inum:
            BA_SIR[i] = 'I'
            ilist[t] += 1
            return
        slist[t] += 1
    #  Yes y The chance of recovery 
    elif BA_SIR[i] == 'I':
        p = random.random()
        if p < y:
            BA_SIR[i] = 'R'
            rlist[t] += 1
            return
        ilist[t] += 1
    else:
        rlist[t]+=1

def sir(b, y, t):
    global ER_SIR, BA_SIR, slist, ilist, rlist
    n = len(ER[0])
    #  initialization ER_SIR,BA_SIR
    ER_SIR = ['S'] * n
    BA_SIR = ['S'] * n

    #  Initialize the array of daily statistics 
    slist = [0] * t
    ilist = [0] * t
    rlist = [0] * t

    #  Random infection ER A node in the network 
    x = random.randint(0, n - 1)
    ER_SIR[x] = 'I'

    #  Traverse t God , Simulated t God 
    for day in range(t):
        #  Traverse all nodes 
        for node in range(n):
            #  Refresh the double-layer network status once 
            er_sir_one(node, day, b, y)
            ba_sir_one(node, day, b, y)
    #  drawing 
    plt.plot(list(range(t)), slist, linewidth=4,label=u'S')
    plt.plot(list(range(t)), ilist, linewidth=4,label=u'I')
    plt.plot(list(range(t)), rlist, linewidth=4,label=u'R')
    plt.legend()  #  Let the legend work 
    plt.xlabel(u"t")  # X Axis labels 
    plt.ylabel("N(t)")  # Y Axis labels 
    plt.title("SIR model result")  #  title 
    plt.show()

def main():
    generateER(1000, 0.006)
    generateBA(1000, 3, 3)
    sir(0.2, 0.5, 50)


if __name__ == '__main__':
    main()


This code is only for learning and communication , No plagiarism !

Four 、 Result analysis

Input PPT Suggested participation
 Insert picture description here
function , We can get a line chart .

Of course , Before giving the results , Let me explain the initial infection strategy —— Random infection ER A node in the network , This premise is very important , Will greatly affect the results .

This running result is very interesting , There are two main results :

1.“ Infected most nodes , Final viral immunity ”

 Insert picture description here

① Chart analysis

You can see , In the first five days , The virus quickly spread from the first one , The number of initial nodes has been reached 1/2 about , The number of infections peaked , And the number of people recovering is increasing , In the end in 2000 In the case of the number of nodes ,10 There are... In about days 1700 About nodes were infected with the virus and recovered , At the same time, there are still 300 No one is infected , At this time, the epidemic was stopped .

Run it many times , When the parameters remain unchanged , The epidemic situation will basically be in the number of infected nodes 1700 Left and right disappear .
 Insert picture description here

② Reason guess

While infecting most nodes , Nodes have a chance to recover , And after recovery, you can no longer be infected with the virus ( namely R The state cannot transition to I state ), So after infecting most nodes , Most nodes recover in succession , What is shown in the chart is R The number of nodes is increasing .

And why is there 300 Less than one node is not infected ?
This is probably because of the connectivity of the whole network , Some nodes don't have much contact with other nodes , Not infected in only a few contacts , And the infected node just recovered , So there are some nodes that are not infected .

2.“ The virus has disappeared without infecting ”

 Insert picture description here

① Chart analysis

This situation is very interesting , The number of infected nodes is always the number of initial nodes 1, In other words, the virus has never spread .
 Insert picture description here

② Reason guess

stay ER In random networks , Because the set parameters are relatively small , So the connectivity is still poor , It happens that the initial infected node is a node with poor connectivity with other nodes , At the same time, it recovered before it could infect other nodes , At this point, the virus has disappeared , In the chart R Nodes are... From beginning to end 1.

summary

In fact, I Python It's delicious , When I write this assignment, I also write while learning , The idea of writing code is largely copied Java The set of . Of course, language is interlinked , It's just a tool for human beings to operate computers , So this process is not too difficult .

This assignment is still quite interesting , And the running result is also beyond my expectation , But after careful analysis, it is not difficult to infer the reason .
From this experiment, it is inevitable to think of the current epidemic , Of course, the reality must be more complicated than the setting in the title , And the parameter logic will be different , For example, the virus will mutate , non-existent “ Virus immunity ” Logical assumptions , The susceptibility coefficient is also stronger than the set value, etc . But it still simulates the process of influenza transmission to a certain extent .

notes : This code is only for learning and communication , No plagiarism

May we take dreams as horses , Live up to your youth !
Let me share with you

copyright notice
author[Dream chaser],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291302491486.html

Random recommended