信息检索十LinkAnalysis.ppt

湖南大学计算机与通信学院 刘钰峰 社会网络（social network） 任何一种用于建立个体之间联系的自然现象、社会活动或技术机制都可能形成一张网 “朋友关系”（对称，无向图） “知晓关系”（不对称，有向图） “文献引用关系”（不对称，有向图） co-author关系（对称，无向图，成块“clique”） 通电话，通信 病毒传染（生物、计算机） 网页链接关系（不对称，有向图） 还可以考虑不同的“尺度”：网站之间，城市之间，省份之间，国家之间，… Web Graph 研究这些“关系图”有什么意义？ 一阶指标（“入度”） 知晓关系：社会知名度 引用关系：认可程度 “高阶指标” 和一个著名人物“共同发表”论文的“距离”：越短似乎显得越“有荣誉”（例如，Erdos number，/enp） 仅仅是“结构”就可以带来丰富的“语义” 例如省份之间的链接数差别可能有有意义的解释 知名度，声望，重要性，… reputation, prestige, importance, … 完全靠“入度”来评价可能显得比较粗燥（即这种评价模型不一定很准） 认识甲的人可能和认识乙的人一样多，但认识乙的人都是些“重要人物”，于是通常应该认为乙比甲重要 不仅是人，论文也是一样，被重要的文章引用的文章可能就比较重要些 例子：按照入度， 节点1，3同样重要； 2，4同样重要。但 我们似乎感到3比1 重要些，2比4重要些。 在Web之前就有社会网络分析学术领域 文献计量学（bibliometry） 研究文献的贡献程度 哪些文章是“有影响的”文章？ 研究文献的聚类，从而可能得到一个领域发展的状况 co-citation分析，如果a引用了b和c，称b和c有co-citation关系 流行传染病学，侦察、谍报学 发现那些关键节点，删除它们使得其他节点之间的距离显著扩大 模型、指标体系的“合适性”取决于应用目标 图论、线性代数若干概念回顾 图，有向图，邻接矩阵，两节点间的距离（d），节点的半径（r），图的连通，有向图的强连通，连通分支 d(u,v)：从u到v的最短路径的长度 r(u)：最大的距离 c(G)：具有最短半径的节点 矩阵（A），矩阵的转置（AT），行列式（|A|），特征值，特征向量，线性相关性 应用举例：Co-citation分析 给定一个文献的集合，希望表达这些文献两两被同时（同一篇文章）引用的情况 coc[i,j]越大，表示这两篇文章的相关性越强 形成文章之间的邻接矩阵E，使得E[i,j]=1，当且仅当文章i引用了j；否则E[i,j]=0。 这意味着，E的第i列反映文章i被引用的情况； 同时引用文章i和文章j的文章数量等于E[*,i]和E[*,j]在相同的行出现1的个数。考虑到E元素的{0,1}特性，即coc[i,j]=∑E[k,i]E[k,j], k=1,2,…,n 或者coc = ETE 关于声望模型 给定一个群体S，及其在上面的一个“知晓”关系R，于是定义了一个有向“关系图”G。用邻接矩阵E表示，E(i,j)=1，当且仅当i “听说过” j（注意这里没有程度之分）。我们希望确定p(i)：所有个体i∈S的“声望” 模型一：p(i) = ∑E[k,i]，k=1,…,n，即i在G上的“入度”，亦即E的第i列的1的个数 清楚、好计算；但是“不够好” 模型二：p(i) = ∑E[k,i]p(k)，k=1,…,n，即i的声望等于知晓他的人的声望之和 清楚、显得要更“精确些”；但是，好计算吗？ 声望模型二（续） 对于所有i，p(i) = ∑E[k,i]p(k)，k=1,…,n 也就是，记p = (p(1), p(2), …, p(n))T, p = ETp 问题是： 这个方程存在解吗？ 如果存在，如何得到？ 如果不存在，该怎么办？ p = ETp 的不存在例 S = {1,2,3}, R = {1,2,1,3,2,3} E = ((0,1,1),(0,0,1),(0,0,0)) ET = ((0,0,0),(1,0,0),(1,1,0)) 不难看到： 方程的成立?p(1)=0?p(2)=0?p(3)=0 先前那4个点的例子也无解 p = ETp ? (I － ET)p = 0 线性代数讲，此方程组有非0解，仅当行列式|I － ET| = 0 但我们算得|I － ET| = -2 即使有解，还有可能不唯一！ S = {1,2,3}, R = {1,2,2,3,3,1} 不难看出任何 p(1) = p(2) = p(3) 都是解 修改模型 模型三：让i的声望等于知晓他的人的声望之和乘以一个常数（对所有i相同） p(i) = c×∑E[k,i]p(k)，k=1,…,n 与模型二的关系 效果上感觉应该差不多，因为是“共同的常数”，而对我们有