实验一三元闭包现象的数据验证.docx

实验一：三元闭包现象的数据验证
快照一：{(1,2), (1,6), (1,7), (2,3), (2,6), (3,6), (3,7), (4,5), (4,7), (5,6), (6,7)}
快照二：{(1,2), (1,3), (实验一：三元闭包现象的数据验证
快照一：{(1,2), (1,6), (1,7), (2,3), (2,6), (3,6), (3,7), (4,5), (4,7), (5,6), (6,7)}
快照二：{(1,2), (1,3), (1,6), (1,7), (2,3), (2,5), (2,6), (3,6), (3,7), (4,5), (4,6), (4,7), (5,6), (5,7), (6,7)}
快照三：{(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,3), (2,5), (2,6), (2,7), (3,5), (3,6), (3,7), (4,5), (4,6), (4,7), (5,6), (5,7), (6,7)}
你的任务是：给出这些数据反映出的两个当前不是朋友的人的“共同朋友个数”与“在下一快照中成为朋友的概率”之间的关系。
计算“共同朋友个数”（邻接矩阵的相乘）
0 1 1 0 1 0 0 1 1 0 1 0 3 0 0 2 0 3
1 0 0 1 0 1 1 0 0 1 0 1 0 3 2 0 3 0
1 0 0 0 0 1 * 1 0 0 0 0 1 = 0 2 2 0 2 0
0 1 0 0 1 0 * 0 1 0 0 1 0 = 2 0 0 2 0 2
1 0 0 1 0 1 1 0 0 1 0 1 0 3 2 0 3 0
0 1 1 0 1 0 0 1 1 0 1 0 3 0 0 2 0 3
输入：T时刻和T+1时刻n个人之间朋友关系快照（图表示）
输出：
给出反映出的两个当前不是朋友的人的“共同朋友个数”与“在下一快照中成为朋友的概率”之间的关系。√
T时刻和T+1时刻的每个人的聚集系数√
节点A的聚集系数 = A的任意两个朋友之间也是朋友的概率（即邻居间朋友对的个数除以总对数）
T时刻和T+1时刻的每条边的介数
介数：一条边承载的一种“流量”
两个节点A和B，设想1个单位的流量从A到B，均分到它们之间所有的最短路径上
K条最短路径，则每条路径上分得1/k，
若一条边被m条路径共用，则在它上面流过m/k
所有节点对都考虑后，一条边上的累记流量就是它的介数（betweenness）
介数计算的一种算法
从一个节点（A）开始，做广度优先搜索，将节点分层（以便于下面的步骤）两个矩阵树状图矩阵边介质矩阵；路得条数 n
确定从A到其他每个节点的最短路径的条数
确定当从节点A沿最短路径向其他所有节点发送1个单位流量时，经过每条边的流量。
对每一个节点，重复上述过程，累计，除以2，即得每条边的介数。
function B=betweenness_edge(A,a)求网络边介数，BY QiCheng
思想：节点i、j间的最短距离等于节点i、k间最短距离与节点k、j间最短距