社会网络和Web分析-课件

Click to edit Master title style,Click to edit Master text styles kdks dksdf dsf sdfsodf,Second level,Third level,Fourth level,Fifth level,*,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,*,社会网络与,Web,分析,（,social network analysis,）,Mining the Web（第七章）,1,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,社会网络（,social network,）,任何一种用于建立个体之间,联系,的自然现象、社会活动或技术机制都可能形成一张网,“,朋友关系”（对称，无向图）,“知晓关系”（不对称，有向图）,“文献引用关系”（不对称，有向图）,co-author,关系（对称，无向图，成块“,clique”,）,通电话，通信,病毒传染（生物、计算机）,网页链接关系（不对称，有向图）,还可以考虑不同的“尺度”：网站之间，城市之间，省份之间，国家之间，,2,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,研究这些“关系图”有什么意义？,一阶指标（“入度”）,知晓关系：社会知名度,引用关系：认可程度,“高阶指标”,和一个著名人物“共同发表,”,论文的“距离”：越短似乎显得越“有荣誉”（例如，,Erdos number,，,oakland.edu/enp,）,仅仅是,“,结构”就可以带来丰富的,“,语义”,例如省份之间的链接数差别可能有有意义的解释,3,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,知名度，声望，重要性，,reputation,prestige,importance,完全靠“入度”来评价可能显得比较粗燥（即这种评价模型不一定很准）,认识甲的人可能和认识乙的人一样多，但认识乙的人都是些“重要人物”，于是通常应该认为乙比甲重要,不仅是人，论文也是一样，被重要的文章引用的文章可能就比较重要些,例子：按照入度，,节点,1,，,3,同样重要；,2,，,4,同样重要。但,我们似乎感到,3,比,1,重要些，,2,比,4,重要些。,如何用一个模型来刻画这种感觉，使算出来的“重要性”反映这种感觉？,4,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,在,Web,之前就有社会网络分析学术领域,文献计量学（,bibliometry,）,研究文献的贡献程度,哪些文章是“有影响的”文章？,研究文献的聚类，从而可能得到一个领域发展的状况,co-citation,分析，如果,a,引用了,b,和,c,，称,b,和,c,有,co-citation,关系,流行传染病学，侦察、谍报学,发现那些关键节点，删除它们使得其他节点之间的距离显著扩大,模型、指标体系的“合适性”取决于应用目标,5,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,图论、线性代数若干概念回顾,图，有向图，邻接矩阵，两节点间的距离（,d,），节点的半径（,r,），图的中心（,c,），图的连通，有向图的强连通，连通分支,d(u,v),：从,u,到,v,的最短路径的长度,r(u),：最大的距离,c(G),：具有最短半径的节点,矩阵（,A,），矩阵的转置（,A,T,），行列式（,|A|,），特征值，特征向量，线性相关性,6,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,应用举例：,Co-citation,分析,给定一个文献的集合，希望表达这些文献两两被同时（同一篇文章）引用的情况,coci,j,越大，表示这两篇文章的相关性越强,形成文章之间的邻接矩阵,E,，使得,Ei,j=1,，当且仅当文章,i,引用了,j,；否则,Ei,j=0,。,这意味着，,E,的第,i,列反映文章,i,被引用的情况；,同时引用文章,i,和文章,j,的文章数量等于,E*,i,和,E*,j,在相同的行出现,1,的个数。,考虑到,E,元素的,0,1,特性,，即,coci,j=,Ek,iEk,j,k=1,2,n,或者,coc=E,T,E,7,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,关于声望模型,给定一个群体,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,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,声望模型二（续）,对于所有,i,，,p(i)=Ek,ip(k),，,k=1,n,也就是，记,p=(p(1),p(2),p(n),T,p=E,T,p,问题是：,这个方程存在解吗？,如果存在，如何得到？,如果不存在，该怎么办？,一般来讲：这个方程的非,0,解是不存在的！,9,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,p=E,T,p,的不存在例,S=1,2,3,R=,E=(0,1,1),(0,0,1),(0,0,0),E,T,=(0,0,0),(1,0,0),(1,1,0),不难看到：,方程的成立,p(1)=0p(2)=0p(3)=0,一般来讲，,p=E,T,p,，意味着要求,E,T,有特征值,1,，这是很难得的。,10,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,先前那,4,个点的例子也无解,p,=E,T,p,(,I,E,T,),p,=,0,线性代数讲，此方程组有非,0,解，仅当行列式,|,I,E,T,|=0,但我们算得,|,I,E,T,|=-2,11,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,即使有解，还有可能不唯一！,S=1,2,3,R=,不难看出任何 p(1)=p(2)=p(3)都是解,怎么办？,12,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,修改模型,模型三：让,i,的声望等于知晓他的人的声望之和乘以一个常数（对所有,i,相同）,p(i)=c,Ek,ip(k),，,k=1,n,与模型二的关系,效果上感觉应该差不多，因为是“共同的常数”，而对我们有意义的只是“相对声望”,但并不完全等价,!,还是要问：,非,0,解存在吗？如果存在，如何计算？,p=c*E,T,p,13,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,解的存在性,这就是特征值、特征向量的定义方程,注意到,c,只需要在一个系统中保持常量，不同的系统是可以不一样的，,1/c,就是,E,T,的特征值，可以随,p,同时求出来,但这问题就来了！,E,T,最多可能有,n,个不同的特征值,如果是有多个不同的特征值，取那一个为好？,不同的特征值对应有不同的特征向量，我们没有理由认为这不同的特征向量反映出来的节点声望序是一致的,即使是同一个特征值，对应的特征子空间中也可能有多个向量（我们也没理由认为它们反映出来的节点声望序是一致的），应该取哪一个？,还有，特征值、特征向量不是实数怎么办？,p=c*E,T,p,14,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,The Perron-Frobenius Theorem,如果有向图,G,是强连通的，则它的邻接矩阵,A,有一个,唯一的,元素全为正实数的特征向量,v,，且该特征向量属于模最大的特征值,。,注：,这个特征向量的唯一性成立在忽略常数因子前提下,由于,A,是非负的，,v,是非负的，因此,也一定是正实数,注意“强连通”的条件需要满足,Stephane Gaubert,et al,“The Perron-Frobenius Theorem for Homogeneous,Monotone Functions,”HP Lab,Bristol,2019.,15,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,人们认为（,generally preferred,）,也是很自然的，我们就取这样的,对应的,v,但我们此时应该理解和“模型二”的差别了,想一想，万一,A,有一个特征值比这个,更接近,1,，它的特征向量会不会更符合“模型二”的思想？,人们这么“决定”的另一个动机大概就是已经有了一种方便的计算方法（,power iteration,）,Ulrik Brandes,“Visual Ranking of Link Structure,”,Journal of Graph Algorithms and Applications,Vol.7,No.2,pp.181-201(2019),16,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,Power Iteration,（计算“声望”）,给定邻接矩阵,E,，记,1,|,2,|,q,1,是属于,1,的特征向量,初始化向量,p,0,，使得,|p,0,|=1,对于,k=1,2,执行如下步骤,x=E,T,p,k-1,，基本迭代,p,k,=x/|x|,，规格化步骤,可以证明（收敛速度）,|p,k,q,1,|=O(|,2,/,1,|,k,),（我们注意到头两个特征值的差别直接影响收敛速度，越大越快）,17,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,例子（,power iteration,）,收敛到：p=(0.165,0.321,0.230,0.284),我们看到：,3,比,1,重要，,2,比,4,重要；,2,、,4,比,1,、,3,重要,18,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,对网页重要性的评价,PageRank,算法，,HITS,（,Hyperlink Induced Topic Search,）算法,都是为了利用,HTML,网页的链接特点，改善查询的效果,面对海量网络信息，搜索引擎追求的不再是笼统的,precision-recall,，而是要保证在低,recall,下的,precision,，也就是前几十个结果中的准确性,都是,2019,年左右完成的研究工作，,PageRank,促成了,Google,，,HITS,依然有学术上的意义。,19,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,PageRank,对每一篇网页，得到一个独立于查询词的相对“重要性”指标，将这个指标和查询匹配情况结合起来（以及其他因素），形成网页的排序。,“重要性”,入度？,类似于前面讨论的“声望”？（模型三）,从一个新的角度考虑一种模型（能说得更彻底些的）？,20,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP,“,随机访问”模型,设想有一个永不休止、随机在网上浏览网页的人。我们问，在稳态情况下（足够长时间后），他会正在看