第二章数据挖掘算法与实践-a99bfa7272dd

社会网络分析（SNA）社会网络？社会网络是指社会行动者（social

actor）及其间的关系的集合。也可以说，一个社会网络是由多个点（社会行动者）和各点之间的连线（行动者之间的关系）组成的集合。用点和线来表达网络，这个是社会网络的形式化界定。、公司、……、城市、国家贸易关系、朋友关系、……、距离关系对象关系社会网络的数学表达形式图论用于表示一个群体成员之间的关系，由点和线连成的图。矩阵论输入、输出Social

NetworkNODE

ANODE

BA

→

BA

←

B111122220.1040.021111333300.11111555500.012222555500.01222299990.0020333344440.0260.026333355550.0010.0015555666600.01Social

Network

after

SegmentationNODE

ANODE

BA

→

BA

←

BCommunity111122220.1040.0211111333300.11333344440.0260.026.0126666999910.32相关概念1、邻接矩阵(link)2、度数(degree)3、最短路径(shortest

path)4、距离(distance)5、直径(Diameter)6、密度(Density)7、modularity

QLINKS011000101110110110011011011101000110相关概念1、邻接矩阵(link)2、度数(degree)3、最短路径(shortest

path)4、距离(distance)5、直径(Diameter)6、密度(Density)7、modularity

Q有向图无向图邻点的个数与该点相连的线的条数点入度：直接指向该点的点的总数

点出度：该点所直接指向的点的总数点5的度数为：4点10的度数为：2点8的点数为：1（n3）的点入度是：3点出度是：2相关概念1、邻接矩阵(link)2、度数(degree)3、最短路径(shortest

path)4、距离(distance)5、直径(Diameter)6、密度(Density)7、modularity

Q最短路径:

a

path

that

starts

at

u

and

ends

at

v

with

thelowest total

link

weight.距离:

the

lowest total

link

weight

between

two

nodes

uand

v

in

a

graph.网络直径:网络中最长的最短路径距离。要考虑权重密度:指的是一个图中各个点之间联络的紧密程度。固定规模的点之间的连线越多，该图的密度就越大。密度的测量：密度用图中实际拥有的关系纽带l与最多可能存在的关系纽带总数之比来表示，即无向图：密度＝2l/n(n-1)有向图：密度=l/n(n-1)(n表示图的规模，即该图一共有n个点。)与权重无关n1到n4的测地线是：l2l4n1到n5的距离是：3该图的直径是：3（

l2l4

l5、l3l4

l5

）密度：0.5MODULARITY

Q（模块化指标Q）1ikm=整个网络中的总关系数eii

=社群i内的关系数/meij

=社群i中所有节点的度数和/(2m)2Q(

munities)

ii

ij1ik1jk(e(

e

)

)

iii

(e

a

2

)算法大社群小社群聚合邻接矩阵0

00

00

10

1

0

0100100度数22

22

可能分割P0

的模块化指标QCommunityeiiaia

2ieii

–

a

2i101/41/16-1/16201/41/16-1/16301/41/16-1/16401/41/16-1/16Q-1/4SumCommunityeiiaia

2ieii

–

a

2i11/21/21/41/4201/41/16-1/16301/41/16-1/16Q1/8P1的模块化指标QCommunityeiiaia

2ieii–

a

2i11/23/49/16-1/16201/41/16-1/16Q-1/8P2的模块化指标Q优化模块化指标Q模块化指标Q结果汇总“中心性”的研究意义：“权力”在社会学中是一个非常重要的概念。一个人之所以拥

力，是因为他与他者存在

关系，可以影响他人。在一个群体中，

如何去界定某个人的权利大小？社会网络学者就

从“关系”的角度出发，用“中心性”来定量

研究权力。人或者组织在社会网络中具有怎样

的权力，或者说居于怎样的中心地位，这一思

想是社会网络分析者最早探讨的内容之一。相关概念1、点度中心性点度中心度（degreecentrality）2、中间中心性3、接近中心性点度中心度无向图中，点的绝对中心度即为该点的邻点数。有向图中内中心度

点入度外中心度

点出度in-degreeout-degree描述图中任何一点在网络中占据的

性相关概念1、点度中心性2、中间中心性（betweenness

centrality）点中间中心度关系中间中心度3、接近中心性点u出现在s、t最短路径上的次数/s、t的最短路径条数u-v关系纽带出现在s、t最短路径上的次数/s、t的最短路径条数将u-v关系看作一个整体后，网络可能会

有的总的关系数注：中间中心度高的点或关系纽带，是信息守门员1－4－5是

接1和5的测地线，1和5之间的测地线仅此一条，4的中间中心度为1。2－4－5是

接2和5的测地线，

2和5之间的测地线仅此一条，4的中间中心度多了1。3

－4－5是

接3和5的测地线，3和5之间的测地线仅此一条，

4的中间中心度又多了1。1

－4－3是

接1和3的测地线，

1和3之间的测地线有2条（

1

－4－3

和1

－2－3

），4的中间中心度赋予1/2。

所以，行动者4的中间中心度为：1+1+1+1/2=3.5，记作CB(4)=3.5,在此基础上标准化相关概念1、点度中心性2、中间中心性3、接近中心性（closeness

centrality）有路径处理无路径处理点u、v之间的最短路径距离特点：接近中心度与权重之间负相关，权重越大，该点对距离对接近中心度的贡献越小无路径处理无路径两点间距离当做0处理，并标准化无路径两点间距离取网络直径无路径两点间距离取节点数“中心性”总结刻画的是行动者的局部中心指数，测量网络中行动者自身的交易能力，没有考虑到能否控制他人点度中心度研究一个行动者在多大程度

上居于其他两

个行动者之间，因而是一种“控制能力”指数中间中心度考虑的是行