当前位置:首页 > 服务端 > 社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断)

社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断)

学习资源来自,一个哲学学生的计算机作业 (karenlyu21.github.io)


1、背景问题

本讲的主题是,社会网络在什么情况下是平衡的,什么情况下不是?

在一个社会中,两个人的关系可能是友善的,也可能是互相抱有敌意的。为了模拟这种现象,我们可以把社会网络中某两个节点之间的边,标注为正关系(友)或负关系(敌)。对于网络中的一个三角结构,我们就可以讨论它是否平衡。

  • 平衡结构有以下两种。这在直观上也很好理解,如果三个人互为好友(左图),或者两个关系很好的人同时看不上第三个人(右图),是没有其他的因素打破这种关系的,这就可以长时间维持。

社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断) _ JavaClub全栈架构师技术笔记

  • 不平衡结构也是以下两种。如果两个人关系不好但有一个共同朋友(左图),这个共同朋友就很难做人,要么倒向其中一边,要么努力让他俩冰释前嫌。如果三个人互有敌意(右图),敌意稍轻的两个人就有动力联合起来,共同对付第三个人。

社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断) _ JavaClub全栈架构师技术笔记

在一个社会网络中,如果所有三角关系都是平衡的,那么这个网络就是平衡的;否则,总有力量改变其中的某个三角关系,从而影响网络结构的平衡性。这个定义可以进一步操作化——结构平衡定理:

一个边标注完全图是平衡的,当且仅当它的所有边都是“+”边或节点集能划分为两个子集,子集内部都是“+”边,子集之间都是“-”边。

也就是说,这一网络要么全部是正关系,要么可以表示为如下的结构:

社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断) _ JavaClub全栈架构师技术笔记

简单的归谬法就可以证明这一定理。如果左边的关系中存在负关系,设节点B和节点C之间为“-”边,那么ABC就是“++-”的不稳定关系。如果右边的关系中存在正关系,设节点B和节点C之间为“+”边,那么ABC就是“++-”的不稳定关系。

可是,社会网络中并非所有节点之间都有边,不是所有边都身处一个或多个三角关系中,逐个考察三角关系的方法不再适用。对于不完全网络图,我们如此理解它的平衡状态:不会因为增加一条标注边,出现不可避免的不平衡三角子图。例如下图,当两个本无关系的人B和D,处在两个潜在的三角关系ABD和BCD中,ABD要求BD为“+”关系,BCD要求BD为“-”关系。不管加上的BD边是什么,这幅图都会出现不平衡三角子图。

社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断) _ JavaClub全栈架构师技术笔记

也就是说,一个平衡的不完全网络图,可以通过补充缺失的边(带极性),成为一个平衡的完全网络。根据结构平衡定理,平衡的不完全网络图的定义也可以进一步操作化:

若已有边不全是“+”,则节点可以分成两组,组内边均为“+”,跨组边均为“-”。

2、计算实践

2.1、作业描述与算法思路

接续上文,要判断不完全网络图是否平衡,我们已经有了一个操作化定理:

若已有边不全是“+”,则节点可以分成两组,组内边均为“+”,跨组边均为“-”。

但这距离算法化还有一定距离。为了算法化,我们还要进一步用到图论的知识:一个含有奇数个“-”的圈的节点不能被分成这样两组:每一组内部的关系都为“+”,跨组的边均为“-”。

也就是说,如果图中存在一个含有奇数个“-”的圈,就没有可能将其节点安排到两个对立阵营中;反过来,若没有那样的圈,则总是可以将所有节点做两个阵营的划分。根据上述操作化定理,如果图中存在一个含有奇数个“-”的圈,该图就不平衡;反之就平衡。

为了更方便地判定网络中是否存在含有奇数个“-”的圈,我们可以整体考虑内部边均为“+”的节点子集,因为它们并不会影响自己所在的圈有多少个“-”。把内部边均为“+”的节点集合为一个“连通分量”,从而把网络简化为“简约图”。这样,简约图里所有的边都是“-”边。例如,下图左侧的不完全社会网络(红边为“+”、黑边为“-”),就可以表示为右侧的简约图。

社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断) _ JavaClub全栈架构师技术笔记

现在,我们只需要考虑简约图里有没有长度为奇数的圈。判定方式是“广度优先搜索”(Breadth First Search or BFS)。在下图的例子中,对左侧的图以节点G为起点做广度优先搜索,所有节点被归入到1–3层里。

社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断) _ JavaClub全栈架构师技术笔记

从广度优先搜索的结果可以看到,圈的形成有两种方式:

  • 下位节点(层数更高的节点)与两个上位同层节点都有边(如E与D、F都有边,形成圈GFED)。这种方式方式形成的是偶数边的圈;因为,每个边都是跨层边,对于一组相邻层(如层1和层2),这个圈都会跨两次(如DE和EF就跨了层1和层2两次,形成圈GFED)。
  • 同层的两个节点之间有边(如AB,形成圈DEABC)。这种方式则会形成奇数边的圈,除了跨两次相邻层以外,这个圈还在层内有一条边(如AB,形成圈DEABC)。

这样,要判断不完全网络图是否平衡,我们只需要BFS结果中是否存在同层边。

2.2、编程实现与要点说明

首先,我们还是需要调用读取数据文件的函数,把邻接矩阵存储在一个numpy 2d-array array里。

def arrayGen(filename):
    f = open(filename, 'r')
    r_list = f.readlines()  # 返回包含size行的列表, size 未指定则返回全部行
    f.close()
    A = []
    for line in r_list:
        if line == '\n':
            continue
        line = line.strip('\n')
        line = line.strip()  # 用于移除字符串头尾指定的字符(默认为空格或换行符)或字符序列,不能删除中间字符
        row_list = line.split()  # 通过指定分隔符对字符串进行切片
        for k in range(len(row_list)):
            row_list[k] = row_list[k].strip()
            row_list[k] = int(row_list[k])
        A.append(row_list)
    n = len(A[0])
    A = np.array(A)
    return A, n


filename = input('请输入邻接矩阵文件名:')
array, n = arrayGen(filename)

一个数据文件的例子如下:

0  1  1  0  0  0  0  0  0  0  0  0  0  0  0
1  0  1 -1  1  0  0  0  0  0  0  0  0  0  0
1  1  0  0  0 -1  0  0  0  0  0  0  0  0  0
0 -1  0  0  0  0 -1  0 -1  0  0  0  0  0  0
0  1  0  0  0 -1  0  0  0  0  0  0  0  0  0
0  0 -1  0 -1  0  0  1  0  0 -1  0  0  0  0
0  0  0 -1  0  0  0  0  0  0  0  1  0  0  0
0  0  0  0  0  1  0  0  0  0 -1  0  0  0  0
0  0  0 -1  0  0  0  0  0  0  0  1  0  0  0
0  0  0  0  0  0  0  0  0  0 -1  1  0  0  0
0  0  0  0  0 -1  0 -1  0 -1  0  0 -1 -1  0
0  0  0  0  0  0  1  0  1  1  0  0  1  0  0
0  0  0  0  0  0  0  0  0  0 -1  1  0  0 -1
0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1
0  0  0  0  0  0  0  0  0  0  0  0 -1 -1  0

第一步,我们先要把网络简化为简约图。先写一个函数cluster,找出节点i所处的连通分量group,其中所有边都是“+”边。这个函数用到了递归,我先以i为起点,找到和它以“+”边相连的节点j,再以j为起点做同样的操作(这其实也是“广度优先搜索”),直到找不到更多以“+”边相连的节点。

def cluster(array, i, group):  # group;连通分量
    group.append(i)
    for j in range(len(array)):
        if j not in group:
            if array[i][j] ==1:
                cluster(array, j, group)
    return group

循环调用cluster函数,每次的搜索起点是还未归入某一连通分量的节点,直到把网络中所有节点都归入某一连通分量。结果存储在groups中。

groups = []
cnt = 0
start = 0
rest = [i for i in range(n)]
while True:
    groups.append([])
    groups[cnt] = cluster(array, start, groups[cnt])
    for j in groups[cnt]:
        rest.remove(j)
    if rest == []:
        break
    start = rest[0]
    cnt += 1
print('连通分量如下:')
print(groups)

以下是一个输出结果的例子:

连通分量如下:
[[0, 1, 2, 4], [3], [5, 7], [6, 11, 8, 9, 12], [10], [13], [14]]

寻找连通分量的过程,并未一一检查内部的所有边。以特定次序找“+”得出的节点集合,在另一种找边的次序中可能存在“-”边。因此我们还需要重新检查一下连通分量内部是否有“-”边。如果有的话,我们可以直接确定这一网络不平衡,因为这一连通分量内部有“++-”的不稳定关系。

innerGroup = False
for group in groups:
    for a in range(len(group)):
        node1_1 = group[a]
        if innerGroup == False:
            for node1_2 in group[a+1:]:
                if array[node1_1][node1_2] == -1:
                    innerGroup == True
                    break
if innerGroup == True:
    print('*****连通分量内部有负边,该网络不平衡。*****')
    print('*****该网络不是平衡网络。*****')
    sys.exit(0)

如果连通分量内部没有“-”边,我们就可以使用groups的信息生成简约图array2。我们检查连通分量之间是否有边(只可能是“-”边),从而确定表示简约图的矩阵在每一格应该填什么。有边就填1,无边就填0。

array2 = np.zeros((cnt+1, cnt+1))  # 简约图
for i in range(len(groups)):
    group = groups[i]
    for j in range(i+1, len(groups)):
        next = groups[j]
        edgeExist = False
        for node1 in group:
            if edgeExist == True:
                break
            for node2 in next:
                if array[node1][node2] == -1:  # 有边
                    array2[i][j] == 1  # 定义有边为1
                    array2[j][i] = 1
                    edgeExist = True
                    break
print('简约网络图如下:')
print(array2)

输出如下:

简约网络图如下:
[[0. 1. 1. 0. 0. 0. 0.]
 [1. 0. 0. 1. 0. 0. 0.]
 [1. 0. 0. 0. 1. 0. 0.]
 [0. 1. 0. 0. 1. 0. 1.]
 [0. 0. 1. 1. 0. 1. 0.]
 [0. 0. 0. 0. 1. 0. 1.]
 [0. 0. 0. 1. 0. 1. 0.]]

接着,我们对简约图做广度优先搜索:输入起点节点,输出搜索结果(每一层有哪些节点layers,节点之间的边有哪些layerCon)。这一过程依靠函数bfs完成。

layers = []
layerCon = []
counted = [0]  # 已经被搜到的节点
def bfs(i_list, layerNum, array = array2):
    global layers
    global layerCon
    global counted
    layers.append([])  # 新建一层
    layerCon.append([])

搜索时,我用到了递归,搜索到下一层的节点j_list后,再以j_list里的节点为起点搜索再下一层,直到搜不到更多节点j_list == []

    j_list = []  # 下一层的节点
    for i in i_list:
        layers[layerNum].append(i)
        if len(counted) == len(array):
            break
        for j in range(len(array[i])):
            if j not in counted:
                if array[i][j] == 1:
                    layerCon[layerNum].append([i, j])
                    j_list.append(j)
    j_set = set(j_list)
    j_list = list(j_set)  # 去除重复节点
    for j in j_list:
        counted.append(j)
    layerNum += 1
    if j_list != []:
        bfs(j_list, layerNum)  # 递归, 从下一层开始
    return layers, layerCon

layers, layerCon = bfs([0], 0)
print('layers:')
print(layers)
print('层间边:')
print(layerCon)

输出结果如下:

layers:
[[0], [1, 2], [3, 4], [5]]
层间边:
[[[0, 1], [0, 2]], [[1, 3], [2, 4]], [[3, 6], [4, 5]], []]

有了搜索结果,我们就可以两两检查每层内的节点,判断层间边是否存在。

innerLayer = False

for layer in layers:
    layerI = layers.index(layer)
    for x in range(len(layer)):
        i = layer[x]
        for j in layer[x+1]:
            if array2[i][j] == 1:  # i与j之间有层间边
                innerLayer = True

if innerLayer == True:
    print('*****层内有边,该网络不平衡。*****')
else:
    print('*****无层内边。*****')

if innerLayer == False:
    print('*****该网络为平衡网络。*****')
else:
    print('*****该网络不是平衡网络。*****')

存在层内边时,我们还可以用一个函数circleSpotter找出奇数圈:输入两个起点节点编码(初始为存在层内边的两个节点编码ij)、它们在哪一层layerI、已经找到的奇数圈节点oddCir(初始为[i,j])、广度优先搜索的结果layerslayerCon;返回所有奇数圈节点。

def circleSpotter(i, j, layerI, oddCir, layerCon = layerCon, layers = layers):

定义一个局部函数nodeAdder,它的作用是,当我们找到起点节点所在的层内边edge后(如i→i2),我们把i2加入oddCir当中,并把i2确定为新的起点节点,以便进行下一轮搜索。

    def nodeAdder(edge, x):
        for node in edge:
            if node != i and node in layers[layerI-1]:
                oddCir.append(node)
                i2 = node
        return oddCir, i2

给定ij,分别调用nodeAdder函数,沿着ij所在的层间边,确定下一组起点节点(在更高层)i2j2

    i_counted = False
    j_counted = False
    for edge in layerCon[layerI-1]:
        if i in edge:
            if i_counted == True:
                continue
            oddCir, i2 = nodeAdder(edge, i)
            i_counted = True
        elif j in edge:
            if j_counted == True:
                continue
            oddCir, j2 = nodeAdder(edge, j)
            j_counted = True

i2j2为新的起点节点继续搜索(递归),直到两条搜索线路汇集于同一点i2 == j2

    layerI -= 1
    if i2 != j2:
        circleSpotter(i2, j2, layerI, oddCir)  # 递归, 从上一层开始
    oddCirSet = set(oddCir)
    oddCir = list(oddCirSet)  # 确保没有重复
    return oddCir

对于每一条层间边,我们都可以调用circleSpotter函数,找出它所在的奇数圈。下述代码中自oddcnt += 1始。

注:对oddcntoddCirs做ignore unresolved reference操作,否则会报错

for layer in layers:
    layerI = layers.index(layer)
    for x in range(len(layer)):
        i = layer[x]
        for j in layer[x+1:]:
            if array2[i][j] == 1:
                innerLayer = True
                oddcnt += 1
                oddCirs.append([i, j])
                oddCir = oddCirs[oddcnt]
                oddCir = circleSpotter(i, j, layerI, oddCir)
                oddCirs[oddcnt] = oddCir

输出结果如下:

*****层内有边,该网络不平衡。*****
构成奇数边数的圆的节点如下:
[[0, 1, 2, 3, 4]]
*****该网络不是平衡网络。*****

3、完整代码

极化关系下网络结构的稳定平衡性

import numpy as np
import sys


def arrayGen(filename):
    f = open(filename, 'r')
    r_list = f.readlines()  # 返回包含size行的列表, size 未指定则返回全部行
    f.close()
    array = []
    for line in r_list:
        if line == '\n':
            continue
        line = line.strip('\n')
        line = line.strip()  # 用于移除字符串头尾指定的字符(默认为空格或换行符)或字符序列,不能删除中间字符
        row_list = line.split()  # 通过指定分隔符对字符串进行切片
        for k in range(len(row_list)):
            row_list[k] = row_list[k].strip()
            row_list[k] = int(row_list[k])
        array.append(row_list)
    n = len(array[0])
    array = np.array(array)
    return array, n


filename = input('请输入邻接矩阵文件名:')
array, n = arrayGen(filename)


def cluster(array, i, group):  # group;连通分量
    group.append(i)
    for j in range(len(array)):
        if j not in group:
            if array[i][j] ==1:
                cluster(array, j, group)
    return group


groups = []
cnt = 0
start = 0
rest = [i for i in range(n)]
while True:
    groups.append([])
    groups[cnt] = cluster(array, start, groups[cnt])
    for j in groups[cnt]:
        rest.remove(j)
    if rest == []:
        break
    start = rest[0]
    cnt += 1
print('连通分量如下:')
print(groups)


innerGroup = False
for group in groups:
    for a in range(len(group)):
        node1_1 = group[a]
        if innerGroup == False:
            for node1_2 in group[a+1:]:
                if array[node1_1][node1_2] == -1:
                    innerGroup = True
                    break
                    
                    
if innerGroup == True:
    print('*****连通分量内部有负边,该网络不平衡。*****')
    print('*****该网络不是平衡网络。*****')
    sys.exit(0)

    
array2 = np.zeros((cnt+1, cnt+1))  # 简约图
for i in range(len(groups)):
    group = groups[i]
    for j in range(i+1, len(groups)):
        next = groups[j]
        edgeExist = False
        for node1 in group:
            if edgeExist == True:
                break
            for node2 in next:
                if array[node1][node2] == -1:  # 有边
                    array2[i][j] = 1  # 定义有边为1
                    array2[j][i] = 1
                    edgeExist = True
                    break
print('简约网络图如下:')
print(array2)


layers = []
layerCon = []
counted = [0]  # 已经被搜到的节点
def bfs(i_list, layerNum, array = array2):
    global layers
    global layerCon
    global counted
    layers.append([])  # 新建一层
    layerCon.append([])
    j_list = []  # 下一层的节点
    for i in i_list:
        layers[layerNum].append(i)
        if len(counted) == len(array):
            break
        for j in range(len(array[i])):
            if j not in counted:
                if array[i][j] == 1:
                    layerCon[layerNum].append([i, j])
                    j_list.append(j)
    j_set = set(j_list)
    j_list = list(j_set)  # 去除重复节点
    for j in j_list:
        counted.append(j)
    layerNum += 1
    if j_list != []:
        bfs(j_list, layerNum)  # 递归, 从下一层开始
    return layers, layerCon


oddCirs = []
oddcnt = -1
innerLayer = False
layers, layerCon = bfs([0], 0)


print('layers:')
print(layers)
print('层间边:')
print(layerCon)


for layer in layers:
    layerI = layers.index(layer)
    for x in range(len(layer)):
        i = layer[x]
        for j in layer[x+1:]:
            if array2[i][j] == 1:  # i与j之间有层间边
                innerLayer = True


def circleSpotter(i, j, layerI, oddCir, layerCon = layerCon, layers = layers):
    def nodeAdder(edge, x):
        for node in edge:
            if node != i and node in layers[layerI-1]:
                oddCir.append(node)
                i2 = node
        return oddCir, i2
    i_counted = False
    j_counted = False
    for edge in layerCon[layerI-1]:
        if i in edge:
            if i_counted == True:
                continue
            oddCir, i2 = nodeAdder(edge, i)
            i_counted = True
        elif j in edge:
            if j_counted == True:
                continue
            oddCir, j2 = nodeAdder(edge, j)
            j_counted = True
    layerI -= 1
    if i2 != j2:
        circleSpotter(i2, j2, layerI, oddCir)  # 递归, 从上一层开始
    oddCirSet = set(oddCir)
    oddCir = list(oddCirSet)  # 确保没有重复
    return oddCir

for layer in layers:
    layerI = layers.index(layer)
    for x in range(len(layer)):
        i = layer[x]
        for j in layer[x+1:]:
            if array2[i][j] == 1:
                innerLayer = True
                oddcnt += 1
                oddCirs.append([i, j])
                oddCir = oddCirs[oddcnt]
                oddCir = circleSpotter(i, j, layerI, oddCir)
                oddCirs[oddcnt] = oddCir

if innerLayer == True:
    print('*****层内有边,该网络不平衡。*****')
    print('构成奇数边数的圆的节点如下:')
    print(oddCirs)
else:
    print('*****无层内边。*****')

if innerLayer == False:
    print('*****该网络为平衡网络。*****')
else:
    print('*****该网络不是平衡网络。*****')

作者:我在吃大西瓜呢
来源链接:https://www.cnblogs.com/wangzheming35/p/15866021.html

版权声明:
1、Java侠(https://www.javaxia.com)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。





本文链接:https://www.javaxia.com/server/125513.html

分享给朋友:

“社会科学问题研究的计算实践——3、极化关系下网络结构的稳定平衡性(计算实践:网络结构平衡性的判断)” 的相关文章