Social network analysis -social network analysis

1. K-cores and core decomposition
   The purpose is to find the current graph(G) A maximal subset of (G’), And this subset (G’) Each of the node There are k Of the above numbers neighbour.$\psi (v)=k$ Representative as G’ Of k As we grow older ,v The biggest one that can exist G’ Of k value .
   Pseudo code ：
   Simply put, it means increasing step by step k, And in accordance with the k The value decreases step by step node（ Delete node Give the corresponding node Add his own k value ）, Until some k You can take all node All removed , It's over .

# Bottom-up core decomposition
G'=G
current=0
while G' There is also node when :
    while true:
         Delete all G' in neighbour The number is less than current Of node
        if  No delete node：
            break
    for G' Every existing node:
         to update G Medium psi(v)=current
    current++

2. Forecast each node Of core ceiling -Estimating an upper bound of the core number
   The goal is to find each node Of k(core number) Upper limit , And then use top-down Method . At the beginning, it was assumed that every node Of core number The upper limit is node Of neighbour Count , And then according to neighbour Order from small to large , Check each one one one by one node Satisfied neighbour The number of , Thus, the real upper limit is calculated through the formula .
   Pseudo code :

 Initial psiest=degree=neighbour Number 
for(v in node and node.psiest in range(ki,ke))：
    #  there Z(v) In fact, it's those with v adjacent , But it doesn't count core number Of node, Because it has already been deleted 
    Z(v)= and v The adjacent node u, And psiest(u)<psiest(v)
    #  Confirm current psiest Is higher than the actual value 
    if |N(v)|-|Z(v)|<psiest(v), be ：
        for Z(v) Each of the Node(u), according to psiest Sort , From small to large , Serial number i from 0 Start :
            f=max(|N(v)|-(i+1),psiest(u))
            if f<psiest(v)：
                psiest(v)=f

3. Top-down core decomposition
   Top down decomposition
   The overall idea is to put all node According to them degree Of upper bound Between partitions , Then update their degree, Then match the corresponding node, And use 1 To find the exact value .
   Pseudo code :

for G All in node(v):
  p(v)=0  //deposit
  psiest(v)=v Of neighbour Count 
k_e=degree_max  (degree Refers to the number of neighbors )
k_i=max(k_min,k_e-step)
while true:
     First use 2 Calculate all node Of psiest
    V'=G Medium psiest stay k_i To k_e Between node( Include ki ke)
    if |V'|>=k_i:
        E'=V'  stay G All of the corresponding edge
        G'=(V',E'),  And copy p(v) Value 
         Use 1 Calculated by the modified method in G' Each of them node Of psi,  Use ki As the lower limit 
    for V' All in node(v):
        if  This node(v) Of psi I've calculated ：
            for v All of the neighbour(u):
                p(u)=p(u)+1 
        else:
            #  If not assign It can only prove these node Of psi Smaller than the current range ( Because the first step was deleted node Will not assign psi Of )
            psiest(v)=k_i-1
    #  to update ke and ki
    k_e=k_i-1
    k_i=max(k_min,k_E-step)
    if ke-ki<0:
        break

modified bottom up
G'=G
current=ki
while G' There is also node when :
    while true:
         Delete all G' in (neighbour Count +p(v)) Less than current Of node
        if  No delete node：
            break
    for G' Every existing node:
         to update G Medium psi(v)=current
    current++

4. use core number To find outliers -core number to detect anomalies
   In general core number and degree It's positively related , So it can be used node Of degree rank and core rank To calculate their r value ,r_c=core rank,r_d=degree rank.score=|log(r_c)-log(r_d)|
   5. use core To detect the best communicators -Core numbers to detect top spreaders
   First we need to simplify G, Simplified as G_C, be called degeneracy core, It's a simplified version G, All that is node Of core number All are G The largest of . And our best communicator is degeneracy core And eigenvector centrality(x(v)) Is used to calculate node How central is it .

eigenvector centrality
for G_c All of the node(v):
    v Of centrality, That is to say x(v)=1/G_c in node The number of 
Normalize(G_c)
for i in rang(1,max):
    for G_c All in node:
         Record the current x(v), Deposit in xlast(v) in 
    for G_c All in node(v):
        for v All of the neighbour(v'):
            #  to update x(v') Value 
            x(v')+=xlast(v)
    Normalize(G_c)
    e=0
    for G_c All in node(v):
        e=e+|x(v)-xlast(v)|
    if e<V_c The number of *error tolerance:
        break

Normalize( In fact, that is L2 norm, Give Way x(v) Of l2 The sum of distances equals 1)

s=0
for G All in node(v):
    s=s+x(v)^2
for G All in node(v):
    x(v)=x(v)/sqrt(s)

Except calculation centrality, We can still use it SIR Model to calculate node How big is the impact on the surrounding . stay SIR In the model , Every node All belong to one of the following states S(susceptible- Can be infected ),I(infected- Infected ),R(recovered- Restored ),I node According to the infection rate beta infection S node, Then I will recover to R node.
Pseudo code ：
The basic idea is to set a node yes I, Everything else is S, And then let I To infect others , Until there was no node yes I Stop when you're ready , Calculate the average number of infections per round

f(v)=0
for  i in range(1,r+1):
    for G In addition to v All of the node(v')：
        s(v') Set to S # Can be infected 
    s(v) Set to I  # Infected 
    f'=0
    step=0
    while G There is also a status of I Of node when ：
        cnt=0
        for V All in node(v')
            if v' yes I node:
                 Just put v' Change to R node
                for v' All of the neighbour v''( repeatable ):
                    if v'' Status is S, And the random number is less than beta：
                        v'' Turn into I
                        cnt++
        f'=f'+cnt
        step=step+1
    f(v)+=(f'/step)
f(v)=f(v)/r

there beta Generally speaking, it uses 1/ maximal eigen value.