1、社会网络与Web分析（social network analysis）Mining the Web（第七章）1社会网络（social network）任何一种用于建立个体之间联系的自然现象、社会活动或技术机制都可能形成一张网“朋友关系”（对称，无向图）“知晓关系”（不对称，有向图）“文献引用关系”（不对称，有向图）co-author关系（对称，无向图，成块“clique”）通电话，通信 病毒传染（生物、计算机）网页链接关系（不对称，有向图）还可以考虑不同的“尺度”：网站之间，城市之间，省份之间，国家之间，2研究这些“关系图”有什么意义？一阶指标（“入度”）知晓关系：社会知名度引用关系：认可程度
2、“高阶指标”和一个著名人物“共同发表”论文的“距离”：越短似乎显得越“有荣誉”（例如，Erdos number，http:/www.oakland.edu/enp）仅仅是“结构”就可以带来丰富的“语义”例如省份之间的链接数差别可能有有意义的解释3知名度，声望，重要性，reputation,prestige,importance,完全靠“入度”来评价可能显得比较粗燥（即这种评价模型不一定很准）认识甲的人可能和认识乙的人一样多，但认识乙的人都是些“重要人物”，于是通常应该认为乙比甲重要不仅是人，论文也是一样，被重要的文章引用的文章可能就比较重要些例子：按照入度，节点1，3同样重要；2，4同样重要。
3、但我们似乎感到3比1重要些，2比4重要些。如何用一个模型来刻画这种感觉，使算出来的如何用一个模型来刻画这种感觉，使算出来的“重要性重要性”反映这种感反映这种感觉？觉？4在Web之前就有社会网络分析学术领域 文献计量学（bibliometry）研究文献的贡献程度哪些文章是“有影响的”文章？研究文献的聚类，从而可能得到一个领域发展的状况co-citation分析，如果a引用了b和c，称b和c有co-citation关系 流行传染病学，侦察、谍报学发现那些关键节点，删除它们使得其他节点之间的距离显著扩大 模型、指标体系的“合适性”取决于应用目标5图论、线性代数若干概念回顾 图，有向图，邻接矩阵，两节
4、点间的距离（d），节点的半径（r），图的中心（c），图的连通，有向图的强连通，连通分支d(u,v)：从u到v的最短路径的长度r(u)：最大的距离c(G)：具有最短半径的节点 矩阵（A），矩阵的转置（AT），行列式（|A|），特征值，特征向量，线性相关性0)(,xAIxAx6应用举例：Co-citation分析 给定一个文献的集合，希望表达这些文献两两被同时（同一篇文章）引用的情况coci,j越大，表示这两篇文章的相关性越强 形成文章之间的邻接矩阵E，使得Ei,j=1，当且仅当文章i引用了j；否则Ei,j=0。这意味着，E的第i列反映文章i被引用的情况；同时引用文章i和文章j的文章数量等于E*,
5、i和E*,j在相同的行出现1的个数。考虑到E元素的0,1特性，即coci,j=Ek,iEk,j,k=1,2,n或者coc=ETE7关于声望模型 给定一个群体S，及其在上面的一个“知晓”关系R，于是定义了一个有向“关系图”G。用邻接矩阵E表示，E(i,j)=1，当且仅当i“听说过”j（注意这里没有程度之分）。我们希望确定p(i)：所有个体iS的“声望”模型一：p(i)=Ek,i，k=1,n，即i在G上的“入度”，亦即E的第i列的1的个数清楚、好计算；但是“不够好”模型二：p(i)=Ek,ip(k)，k=1,n，即i的声望等于知晓他的人的声望之和清楚、显得要更“精确些”；但是，好计算吗？8声望模型
6、二（续）对于所有i，p(i)=Ek,ip(k)，k=1,n 也就是，记p=(p(1),p(2),p(n)T,p=ETp 问题是：这个方程存在解吗？如果存在，如何得到？如果不存在，该怎么办？一般来讲：这个方程的非0解是不存在的！9p=ETp 的不存在例 S=1,2,3,R=,E=(0,1,1),(0,0,1),(0,0,0)ET=(0,0,0),(1,0,0),(1,1,0)不难看到：方程的成立p(1)=0p(2)=0p(3)=0一般来讲，p=ETp，意味着要求ET有特征值1，这是很难得的。10先前那4个点的例子也无解 p p=ETp p (I I ET)p p=0 0 线性代数讲，此方程组有非
7、0解，仅当行列式|I ET|=0 但我们算得|I ET|=-211即使有解，还有可能不唯一！S=1,2,3,R=,不难看出任何 p(1)=p(2)=p(3)都是解怎么办？12修改模型 模型三：让i的声望等于知晓他的人的声望之和乘以一个常数（对所有i相同）p(i)=cEk,ip(k)，k=1,n 与模型二的关系效果上感觉应该差不多，因为是“共同的常数”，而对我们有意义的只是“相对声望”但并不完全等价!还是要问：非0解存在吗？如果存在，如何计算？p=c*ETp13解的存在性 这就是特征值、特征向量的定义方程注意到c只需要在一个系统中保持常量，不同的系统是可以不一样的，1/c就是ET的特征值，可以随
8、p同时求出来 但这问题就来了！ET最多可能有n个不同的特征值如果是有多个不同的特征值，取那一个为好？不同的特征值对应有不同的特征向量，我们没有理由认为这不同的特征向量反映出来的节点声望序是一致的即使是同一个特征值，对应的特征子空间中也可能有多个向量（我们也没理由认为它们反映出来的节点声望序是一致的），应该取哪一个？还有，特征值、特征向量不是实数怎么办？p=c*ETp14The Perron-Frobenius Theorem 如果有向图G是强连通的，则它的邻接矩阵A有一个唯一的元素全为正实数的特征向量v，且该特征向量属于模最大的特征值。注：这个特征向量的唯一性成立在忽略常数因子前提下由于A是非
9、负的，v是非负的，因此也一定是正实数注意“强连通”的条件需要满足 Stephane Gaubert,et al,“The Perron-Frobenius Theorem for Homogeneous,Monotone Functions,”HP Lab,Bristol,2001.15人们认为（generally preferred）也是很自然的，我们就取这样的对应的v但我们此时应该理解和“模型二”的差别了想一想，万一A有一个特征值比这个更接近1，它的特征向量会不会更符合“模型二”的思想？人们这么“决定”的另一个动机大概就是已经有了一种方便的计算方法（power iteration）Ulri
10、k Brandes,“Visual Ranking of Link Structure,”Journal of Graph Algorithms and Applications,Vol.7,No.2,pp.181-201(2003)16Power Iteration（计算“声望”）给定邻接矩阵E，记1|2|,q1是属于1的特征向量 初始化向量p0，使得|p0|=1 对于k=1,2,执行如下步骤x=ETpk-1，基本迭代pk=x/|x|，规格化步骤 可以证明（收敛速度）|pk q1|=O(|2/1|k)（我们注意到头两个特征值的差别直接影响收敛速度，越大越快）17例子（power iterat
11、ion）收敛到：p=(0.165,0.321,0.230,0.284)我们看到：3比1重要，2比4重要；2、4比1、3重要18对网页重要性的评价 PageRank算法，HITS（Hyperlink Induced Topic Search）算法 都是为了利用HTML网页的链接特点，改善查询的效果面对海量网络信息，搜索引擎追求的不再是笼统的precision-recall，而是要保证在低recall下的precision，也就是前几十个结果中的准确性 都是1996年左右完成的研究工作，PageRank促成了Google，HITS依然有学术上的意义。19PageRank 对每一篇网页，得到一个独立
12、于查询词的相对“重要性”指标，将这个指标和查询匹配情况结合起来（以及其他因素），形成网页的排序。“重要性”入度？类似于前面讨论的“声望”？（模型三）从一个新的角度考虑一种模型（能说得更彻底些的）？20“随机访问”模型 设想有一个永不休止、随机在网上浏览网页的人。我们问，在稳态情况下（足够长时间后），他会正在看哪一篇网页呢？对应这个问题，每个网页v会有一个概率，p(v)；我们可以合理地设想：此时到达v的概率，依赖于上一个时刻到达“链向”v的网页的概率，以及那些网页中超链的个数。即，pk+1(v)=Eu,v*pk(u)/du,over u 这里，du是网页u的“出度”，Eu,v over v。21
13、随机浏览模型（continue）改写一下，成ukukupdvuEvp)(,)(1kTkukupLpupvuLvpdvuEvuL11,或者写成矩阵形式，于是，令，形式上和“声望”模型一样，只是矩阵L有行向量元素和为1的性质。有用吗？22Stochastic matrix 矩阵M，元素非负，每个列向量元素之和分别都等于1（亦称马尔科夫转移矩阵）LT就是这种随机矩阵 显然，随机矩阵的最大左特征值为1，对应的特征向量是全1元素向量 由于转置矩阵的行列式和原矩阵的行列式相等，矩阵的左特征值集合和右特征值集合相等xMx于是1也就是LT最大的特征值！23还有一点问题 上述“随机浏览”模型有效的条件是：由网页
14、形成的有向图允许通过链接关系访问到每一个网页 但有两个情况是破坏这条件的有入度或者出度为0的点图中形成“圈”因此该模型的表述通常要求所形成的图是irreducible（强连通）和aperiodic（不能有进去后出不来的圈）。24但我们还得解决实际问题：修改模型 让这浏览者每次以一定的概率（1-）沿着超链走，以概率（）重新随机选择一个新的起始节点这在物理意义上即总是有可能跳进入度为0的点，跳出那些“圈”。在模型表达上即为iNTiNiTipNLpNpLp)1()1(1)1(1剩下来的迭代就可用 power iteration,选在0.1和0.2之间（我们注意到，此时又没有了特征值为1的漂亮性质）2
15、5HITS 从设计思想来看，HITS和PageRank的一个基本区别是HITS针对具体查询、应用在查询时间，而PageRank是独立于查询的 Root set,R(q):和查询q相关的网页集合 Base set,V(q):除了R(q)外，还包括指向R(q)元素和被R(q)元素指向的网页 Expanded set=V-R 两个概念（直觉上有意义）AUTHORITY（权威型网页）：内容权威，质量高的网页HUB（目录型网页）：指向许多authority网页的网页26Authority and Hub scores 针对uV(q)，在每个网页u上定义有两个参数：au和hu，分别表示其权威性和目录性。交
16、叉定义一个网页u的a值依赖于指向它的网页v的h值一个网页u的h值依赖于它所指的网页v的a值hEEaEhhEaTT27HITS(contd.)声望高的（入度大）权威性高 认识许多声望高的（出度大）目录性强 如何计算？Power Iteration on:hEEaEhaEEhEaTTT28HITS算法过程（Topic Distillation）1.Send query to a text-based IR system and obtain the root-set.2.Expand the root-set by radius one to obtain an expanded graph.3.
17、Run power iterations on the hub and authority scores together.4.Report top-ranking authorities and hubs.29小结 网页的相互链接特性，使得我们可以应用社会网络分析的方法来从网页集合的结构中提炼有用的信息（语义）提炼什么信息？取决于我们对应用目标的认识，还取决于有关技术模型的精确定义、有效计算，以及对可能产生误差的认识和评估 PageRank和HITS是两个经典的例子，大目标一致，切入点不同。它们不应该意味着不可能有更好的（或者更有特色的）新角度它们的一个本质缺陷是：将网页之间的链接关系“太当真”。3031
