社会网络分析-Social Network Analysis

1. K-cores and core decomposition
   目的是为了找到当前graph(G)的一个最大子集(G’)，且这个子集(G’)中的每个node都有k以上个数的neighbour。$\psi (v)=k$ 代表当G’的k越来越大时，v所能存在的最大的那个G’的k值。
   伪代码：
   简单来说就是一步步增加k，并按照k值一步步减少node（删除node时给对应的node加上他自己的k值），直到某个k可以将所有node都移除，就结束了。

# Bottom-up core decomposition
G'=G
current=0
while G'中还有node时:
    while true:
        删除掉所有G'中neighbour数小于current的node
        if 没删除任何node：
            break
    for G'中现存的每个node:
        更新G中的psi(v)=current
    current++

2. 预测每个node的core上限-Estimating an upper bound of the core number
   目的就是找到每个node的k(core number)的上限，进而使用top-down方法。一开始就是假设每个node的core number上限为此node的neighbour数，然后按照neighbour数量从小到大排序，挨个检查每个node满足条件的neighbour的数量，从而通过公式计算出真实上限。
   伪代码:

初始的psiest=degree=neighbour数量
for(v in node and node.psiest in range(ki,ke))：
    # 这里的Z(v)其实就是那些与v相邻，但是不算进core number的node，因为早已经被删掉了
    Z(v)=和v相邻的node u，且psiest(u)<psiest(v)
    # 确认当前psiest是比实际值更高的
    if |N(v)|-|Z(v)|<psiest(v)，则：
        for Z(v)中的每个Node(u)，按照psiest排序，从小到大，序号i从0开始:
            f=max(|N(v)|-(i+1)，psiest(u))
            if f<psiest(v)：
                psiest(v)=f

3. Top-down core decomposition
   从上而下的分解方式
   整体思路就是将所有的node按照他们degree的upper bound分区间,然后用公式更新一下他们的degree，然后再按照区间匹配对应的node,并用1中的方法找到确切的值。
   伪代码:

for G中的所有node(v):
  p(v)=0  //deposit
  psiest(v)=v的neighbour数
k_e=degree_max  (degree指邻居数量)
k_i=max(k_min,k_e-step)
while true:
    先用2里的方法算出所有node的psiest
    V'=G中的psiest在k_i到k_e之间的node(包括ki ke)
    if |V'|>=k_i:
        E'=V' 在G中对应的所有edge
        G'=(V',E'), 并且复制p(v)的值
        使用1中更改后的方法计算出G'中每个node的psi, 使用ki作为下限
    for V'中的所有node(v):
        if 这个node(v)的psi算过了：
            for v的所有neighbour(u):
                p(u)=p(u)+1 
        else:
            # 如果没assign就只能证明这些node的psi比当前的区间更小(因为第一步就被删掉的node是不会assign psi的)
            psiest(v)=k_i-1
    # 更新ke和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'中还有node时:
    while true:
        删除掉所有G'中(neighbour数+p(v))小于current的node
        if 没删除任何node：
            break
    for G'中现存的每个node:
        更新G中的psi(v)=current
    current++

4. 用core number来找异常值-core number to detect anomalies
   一般情况下core number和degree是正相关的，所以可以用node的degree rank和core rank来计算他们的r值，r_c=core rank，r_d=degree rank。score=|log(r_c)-log(r_d)|
   5.用core来检测最佳传播者-Core numbers to detect top spreaders
   首先我们需要简化G，简化为G_C，叫做degeneracy core，就是简化版的G，其中所有node的core number都是G中最大的。而我们的最佳传播者就在degeneracy core的正中心而eigenvector centrality(x(v))就是用来计算node到底有多中心。

eigenvector centrality
for G_c中所有的node(v):
    v的centrality，也即x(v)=1/G_c中node的数量
Normalize(G_c)
for i in rang(1,max):
    for G_c中所有node:
        记录当前的x(v)，存到xlast(v)中
    for G_c中所有node(v):
        for v的所有neighbour(v'):
            # 更新x(v')的值
            x(v')+=xlast(v)
    Normalize(G_c)
    e=0
    for G_c中所有node(v):
        e=e+|x(v)-xlast(v)|
    if e<V_c的数量*error tolerance:
        break

Normalize(其实就是L2 norm,让x(v)的l2距离之和等于1)

s=0
for G中所有node(v):
    s=s+x(v)^2
for G中所有node(v):
    x(v)=x(v)/sqrt(s)

除了计算centrality，我们还可以用SIR模型来计算node对周边的影响有多大。在SIR模型中，每个node都属于以下的其中一个状态S(susceptible-可以被感染的),I(infected-被感染的),R(recovered-恢复了的)，I node可以按照感染率beta感染S node，然后自己会恢复成R node.
伪代码：
基本思路就是定一个node是I，其他的都是S，然后让I去感染别人，一直到没有node是I了的时候就停下，计算平均每轮感染的人数

f(v)=0
for  i in range(1,r+1):
    for G中除了v的所有node(v')：
        s(v')设为S #可以被感染的
    s(v)设为I  #已被感染的
    f'=0
    step=0
    while G中还有状态为I的node时：
        cnt=0
        for V中所有node(v')
            if v'是I node:
                就把v'变化为R node
                for v'的所有neighbour v''(可重复):
                    if v''状态是S，且随机数小于beta：
                        v''变为I
                        cnt++
        f'=f'+cnt
        step=step+1
    f(v)+=(f'/step)
f(v)=f(v)/r

这里的beta一般来说用的都是1/最大的eigen value。