商务智能原理与方法（第3版）-课件 Lecture7-Social Network

数据挖掘——社会网络分析社会网络与社会一个救命文档的24小时7月19日晚，一份命名为“待救援人员信息”的汇总文档在网络传播。此文档的作者是上海财经大学2017级学生李睿。思考：社会网络的社会价值是什么？社会网络的哪些特征能够带来这些价值？怎样理解“所有人写所有人”时代中的信息共享与协同？哥尼斯堡七桥问题1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文图论与几何拓扑六度分割理论任何两人之间联系，平均中间只通过5个人1967年Milgram实验300信件传递Kansas农场主->Massachusetts神学院学生的妻子(3次传递)KevinBacon游戏Bacon合演电影，Bacon数为1Google的Bacon数检索工具复杂网络的”小世界”特性强关系与弱关系人脉Socialcapital(社会资本)ConnectionGuanxi强关系有价值的人脉关系一起同过窗，一起扛过枪弱关系若即若离的那个“Ta”强关系与弱关系20世纪70年代，MarkGranovettter的研究波士顿近郊居住的人怎么找到工作282人中随机抽取100人100人中54人通过个人关系找到工作靠什么关系找到工作？16.7%每周至少见两次面55.6%每周见不到两次，每年至少一次27.8%一年也见不到一次大多数用到的关系，是那些不怎么联系的老同学或同事强关系与弱关系强关系增加同质化程度弱关系告诉你一些你不知道的事情连接不同的社交群体，从圈外提供信息强关系与弱关系2012年，FaceBook强关系互相评论对方发的状态反之是弱关系社交媒体加剧了“物以类聚，人以群分”？人们禁锢在自己的社交圈“孤岛”？分享链接的行为独自发现P1朋友发链接，看了之后转发P2强关系的信息转发的概率是弱关系的两倍以上强关系与弱关系我们愿意转发强联系，但是。。。强弱关系的放大效应不同一条信息通过朋友转发看到的概率/独自看到的概率强关系的放大效用6弱关系的放大效用9强联系告诉的信息，我们也有可能发现没有弱关系，有些信息很难发现走出去追求“弱关系”复杂网络分析发展的重要事件时间任务事件1736年Euler七桥问题1959年Erdos和Renyi随即图理论1967年Milgram小世界实验1973年Granovetter弱连接的强度1998年Watts和Strogatz小世界模型1999年Barabasi和Albert无标度网络复杂网络相关概念网络的平均距离（averagedistance）网络的簇系数（clusteringcoefficient）网络中所有节点对的最短距离的平均值对于某个节点，它的所有相邻节点之间连的数目占可能的最大连边数目的比例，网络的簇系数是所有节点簇系数的平均复杂网络的统计特征小世界特征（small-worldproperty）无标度特征（scale-freeproperty）随机网络（RandomNetworks）复杂网络（ComplexNetworks）两个节点之间的边存在与否不再确定，而是根据一个概率确定既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络复杂网络相关概念规则网络具有大的簇系数、大的平均距离随机网络具有小的簇系数、小的平均距离大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应，具有这种效应的网络就是小世界网络在规则网络上以一个很小的概率添加新的连边，使得原有的网络平均距离缩短真实网络几乎都具有小世界效应复杂网络相关概念大量真实网络除具有小世界效应之外，还具有无标度特征节点度指的是该节点拥有相邻节点的数目节点度服从幂律分布是指某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似表示随机网络和规则网络的度分布区间非常窄，几乎找不到偏离节点度均值较大的点，故其平均度可看作节点度的一个特征标度复杂网络的幂律分布是一条下降相对缓慢的曲线，这使得网络中存在度很大的节点节点度服从幂律分布的网络叫无标度网络，并称这种节点度的幂律分布为网络的无标度特征邓巴数字RobinDunbar认为人类社会网络的平均规模是150Hill,R.A.,andDunbar,R.I.M.Socialnetworksizeinhumans.HumanNature14(2003).数字和人类工作记忆的容量大小相关社交=沟通？社会网络分析15社会网络分析不关注个体规范或者独立群体的共同活动关注人们的联系如何影响他们行动中的可能性和限制始于20世纪30年代，由社会心理学家莫雷诺Moreno创立在一个社会网络中，谁是明星人物？谁是边缘人物？谁是八卦传播者，谁是沟通的桥梁？内容安排社会网络中心性社会网络的权威引用社会网络社会网络的链接分析社会网络的中心性网络中谁更重要发现名人一个人在组织中的权力与他“钥匙圈上的钥匙数量”成反比(ScottAdams)度中心性贴近中心性中介中心性度中心性反映某一个特定节点拥有与其他参与者的链接或者链接数目在无向图和有向图中是不同的在无向图中，参与者i的度中心性就是i的度与最大度n-1之间的比值在有向图中，对于某一个节点，主要考虑一个节点的链出链接贴近中心性认为一个参与者如果与其它参与者之间的距离足够近，这个参与者就位于中心使用最短距离来度量两个节点之间的距离假设两个节点i和j之间的最短距离为d(i,j)无向图中，节点i的贴近中心性的定义为有向图中，节点i和j之间的最短距离有时不存在中介中心性如果两个节点k和j想要彼此联系上，而节点i处在连接它们的路径上，那么节点i对于连结节点k和j起到一定的作用对于节点i而言，如果它处于更多节点对之间的路径上，那么节点i对于其他节点的控制能力更强，节点i应处于整个网络的中心中介中心性在无向图中，节点i的中介中心性定义pjk表示节点j与节点k之间的最短路径数目，pjk(i)表示节点j与节点k之间经过节点i的最短路径数目在无向图中，如果每一对节点都满足上述的理想情况，则节点i的中介中心性最大归一化中介中心性节点i的中介中心性最大中介中心性(3/3)2499:instituteleader2228:chiefdirectorofteachingoffice1126:directorofIT/ISoffice中介中心性有向图当中，依然用类似无向图中的方式计算中介中心性节点k到节点j最短路径不同于节点j到节点k之间的最短路径对于一个节点i，归一计算结果为社会网络的权威在社会网络中，一个节点如被大量其它节点指向，这个节点具有非常高的权威在通过链接形成的网页网络中，如果一个网页被多个网页中的链接所指向，那么这个网页一定非常具有权威性权威与中心性权威（Prestige）相比于中心性而言，是对节点重要性的一个更加精妙的度量方式权威只能在有向图中计算中心性可以在有向图和无向图中计算权威则重点考虑一个节点的入度中心性只考虑一个节点的出度三种常用的权威性度权威邻近权威等级权威度权威度权威（DegreePrestige）从一个节点度的角度来衡量一个节点的权威如果一个节点有多个链入链接，这个节点一定具有高权威度量一个节点的权威入度越大，则该节点的权威越高邻近权威度权威仅考虑与节点i相邻的参与者对于节点i，Ii表示能够到达该节点的所有节点的集合，该集合称作节点i的影响区域用d(j,i)表示节点j到节点i的最短路径长度，其中每条边的距离都是1。这样集合Ii中的平均距离即忽略通过间接的方式依然可以到达i的节点邻近权威对于节点i，影响区域占全体节点的比率为：对于一个节点i，如果这个节点的影响区域越大，说明这个节点的权威越高如果节点i的影响区域中的节点到达节点i的平均距离越小，则节点i的权威也越高。等级权威在度权威和邻近权威中，都忽略了其他节点的权威如果一个网页得到多个权威性很高的网页的指向链接，这个网页的权威也会很高等级权威也就是一种考虑了其他节点的权威的测度等级权威等级权威PR(i)定义为指向节点i的节点权威的线性组合Aji表示节点j是否指向节点i。如果节点j指向节点i，则Aji=1；否则，Aji=0矩阵A表示网络的邻接矩阵如果有n个节点，那么就会有n个等式如果j指向i，那么Aji=1；否则Aji=0链接模式分析33三元组最基本的链接模式闭合三元组核心家庭第三个节点的作用提供不同的意见增加反馈渠道A-B-C链接模式分析34开放三元组结构洞的作用个体占据的结构洞数量与其作为企业、银行、地产代理的业绩相互关联结构洞禁止进入的三元组B的想法A和C的想法维持信息不对称跨界套利B为银行，A公司存款5%，C公司贷款7%RonaldBurst的研究表明，在一个竞争性的市场中，占据更多结构洞的商人具有更显著的高成功率引用社会网络社会网络分析另外一个应用领域是科技文献之间的引用分析(CitationAnalysis)每一篇学术文章引用不同作者的文献，引用让学术文章之间构成了联系，形成网络同引分析(Co-Citation)引文耦合(BibliographicCoupling)同引分析在科技文献之间，经常存在两篇论文i和j同时被一篇论文k引用的情况同引分析就是利用这样的一种关系来度量论文i和j之间的相似程度同引分析假设有n篇论文，L为其引用矩阵引用矩阵L中的第i行第j列的元素Lij表明两篇论文i和j之间的引用关系如果论文i中引用了论文j，则Lij=1论文i没有引用论文j，则Lij=0同时引用论文i和j的论文数Cij引文耦合在引文耦合中，如果计算同时被论文i和论文j引用的论文数社会网络中的链接分析社会网络的链接分析中经典方法PageRank算法1998年提出GoogleHITS算法1999年提出PageRank&

网页排名PageRank是由谷歌创始人SergeyBrin和LawrencePage提出，它的成功很大程度要归功于谷歌的商业成功PageRank的经典应用：网页排名一种静态的网页评级算法为每个网页离线计算PageRank值而且该值与查询内容无关。PageRank算法依赖于Web的自然特性，它利用Web的庞大链接结构来作为单个网页质量的参考。PageRank将网页之间按照链接的方式组成一个网络从其他网页指向网页i的链接。不考虑来自同一网站的链接每个网页的PageRank值就可以看做该网页的权威值网页i的链入链接从网页i指向其他网页的链接。也不考虑来自同一网站的链接网页i的链出链接PageRankPageRank算法基于如下三点假设如果一个页面被很多其他页面所指向，则这个页面可能是重要的如果一个页面被重要的页面所指向，则这个页面可能是重要的一个页面的重要性均分传播到它指向的页面中PageRank给定4个网页所组成的文档集合{A,B,C,D}转置矩阵M中每一个元素表示相应的列的网页转移到相应行的网页的概率转移矩阵的转置矩阵PageRank转置矩阵M，Mjk是M中第j行第k列的元素，其取值分为两种情况若节点k和节点j之间存在k指向j的边|O(k)|表示节点k的出度，也就是链出链接的个数若两个节点之间不存在k指向j的边，则相应的Mjk=0任意节点j的权威度可按照如下的方法计算：PageRank权威度的定义采用递归的方式，因此可以进行迭代计算每个节点的权威度为1/n，也就是R0(j)=1/n将所有节点权威度构成一个向量R，可利用矩阵运算的方法对R进行迭代PageRank为了使此迭代计算收敛，矩阵M满足要求：M必须不可约(强连通图)，M中任何两个节点都可达在图G中为每个节点增加n条边，指向图中的每一个节点，包括自己本身，这样形成一个新的图G*PageRank改变后的矩阵用M*表示，则新的迭代公式如下所示如果给定初始状态下的权威度为R0=(0.25,0.25,0.25,0.25)TC=0.8按迭代计算公式得到4个网页的权威度结果为R=(0.176,0.176,0.332,0.316)T四个网页的排名结果为<CDAB>PageRank优点防止作弊的发生一个页面的权威和重要性是由指向它的页面所决定的，也就是由该页面的链入链接决定在用户进行检索时，搜索的效率就非常高每一个页面的PageRank值不受查询条件的影响，它只受全局的链接情况影响所有页面的PageRank值都是在离线的情况下计算出来的，而不是在用户查询时计算的PageRank不足PageRank值与查询条件无关的这一特点也会导致一些缺陷用户在查询某一个特定话题时，往往希望得到仅在这一话题上的权威页面，而PageRank所给出的是广泛意义上的权威PageRank算法也没有考虑页面的生成时间，它将新旧页面统一对待针对这一不足，已有很多研究人员提出了考虑时间的PageRank算法（TimedPageRank）HITSHITS算法是英文HypertextInducedTopicSearch首字母缩写HITS算法是与查询相关的当用户提交一个查询请求时，HITS算法首先得到检索系统返回的相关页面，并依此为基础，从链入链接和链出链接两个角度扩展出两个页面集合，并计算页面的评级权威等级（Authorityranking）中心等级（Hubranking）HITS权威网页和中心网页一个有权威（Authority）的网页，意味着这个网页一定拥有数量众多的链入链接。有权威的网页会包含重要或者权威的信息，会得到许多外部网页的信赖和引用一个中心（Hub）的网页，意味着这个网页一定拥有数量众多的链出链接，这些链接分别指向不同的权威网页。一个中心网页作为某个特定话题的组织和集成者，它会指向许多和这个话题相关的权威网页。HITSHITS算法的核心思想是中心网页和权威网页之间存在互相促进的关系好的中心网页一定会有很多的链出链接指向好的权威网页好的权威网页也一定会包含很多好的中心网页的链入链接HITS当用户提交查询条件q之后，检索系统会检索到相关网页，并根据网页的相关性将检索结果排序。HITS算法一般选取排名在前200的网页，这些网页与查询条件