數(shù)據(jù)挖掘——社會(huì)網(wǎng)絡(luò)分析社會(huì)網(wǎng)絡(luò)與社會(huì)一個(gè)救命文檔的24小時(shí)7月19日晚，一份命名為“待救援人員信息”的匯總文檔在網(wǎng)絡(luò)傳播。此文檔的作者是上海財(cái)經(jīng)大學(xué)2017級(jí)學(xué)生李睿。思考：社會(huì)網(wǎng)絡(luò)的社會(huì)價(jià)值是什么？社會(huì)網(wǎng)絡(luò)的哪些特征能夠帶來這些價(jià)值？怎樣理解“所有人寫所有人”時(shí)代中的信息共享與協(xié)同？哥尼斯堡七橋問題1736年29歲的歐拉向圣彼得堡科學(xué)院遞交了《哥尼斯堡的七座橋》的論文圖論與幾何拓?fù)淞确指罾碚撊魏蝺扇酥g聯(lián)系，平均中間只通過5個(gè)人1967年Milgram實(shí)驗(yàn)300信件傳遞Kansas農(nóng)場(chǎng)主->Massachusetts神學(xué)院學(xué)生的妻子(3次傳遞)KevinBacon游戲Bacon合演電影，Bacon數(shù)為1Google的Bacon數(shù)檢索工具復(fù)雜網(wǎng)絡(luò)的”小世界”特性強(qiáng)關(guān)系與弱關(guān)系人脈Socialcapital(社會(huì)資本)ConnectionGuanxi強(qiáng)關(guān)系有價(jià)值的人脈關(guān)系一起同過窗，一起扛過槍弱關(guān)系若即若離的那個(gè)“Ta”強(qiáng)關(guān)系與弱關(guān)系20世紀(jì)70年代，MarkGranovettter的研究波士頓近郊居住的人怎么找到工作282人中隨機(jī)抽取100人100人中54人通過個(gè)人關(guān)系找到工作靠什么關(guān)系找到工作？16.7%每周至少見兩次面55.6%每周見不到兩次，每年至少一次27.8%一年也見不到一次大多數(shù)用到的關(guān)系，是那些不怎么聯(lián)系的老同學(xué)或同事強(qiáng)關(guān)系與弱關(guān)系強(qiáng)關(guān)系增加同質(zhì)化程度弱關(guān)系告訴你一些你不知道的事情連接不同的社交群體，從圈外提供信息強(qiáng)關(guān)系與弱關(guān)系2012年，F(xiàn)aceBook強(qiáng)關(guān)系互相評(píng)論對(duì)方發(fā)的狀態(tài)反之是弱關(guān)系社交媒體加劇了“物以類聚，人以群分”？人們禁錮在自己的社交圈“孤島”？分享鏈接的行為獨(dú)自發(fā)現(xiàn)P1朋友發(fā)鏈接，看了之后轉(zhuǎn)發(fā)P2強(qiáng)關(guān)系的信息轉(zhuǎn)發(fā)的概率是弱關(guān)系的兩倍以上強(qiáng)關(guān)系與弱關(guān)系我們?cè)敢廪D(zhuǎn)發(fā)強(qiáng)聯(lián)系，但是。。。強(qiáng)弱關(guān)系的放大效應(yīng)不同一條信息通過朋友轉(zhuǎn)發(fā)看到的概率/獨(dú)自看到的概率強(qiáng)關(guān)系的放大效用6弱關(guān)系的放大效用9強(qiáng)聯(lián)系告訴的信息，我們也有可能發(fā)現(xiàn)沒有弱關(guān)系，有些信息很難發(fā)現(xiàn)走出去追求“弱關(guān)系”復(fù)雜網(wǎng)絡(luò)分析發(fā)展的重要事件時(shí)間任務(wù)事件1736年Euler七橋問題1959年Erdos和Renyi隨即圖理論1967年Milgram小世界實(shí)驗(yàn)1973年Granovetter弱連接的強(qiáng)度1998年Watts和Strogatz小世界模型1999年Barabasi和Albert無標(biāo)度網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)相關(guān)概念網(wǎng)絡(luò)的平均距離（averagedistance）網(wǎng)絡(luò)的簇系數(shù)（clusteringcoefficient）網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)的最短距離的平均值對(duì)于某個(gè)節(jié)點(diǎn)，它的所有相鄰節(jié)點(diǎn)之間連的數(shù)目占可能的最大連邊數(shù)目的比例，網(wǎng)絡(luò)的簇系數(shù)是所有節(jié)點(diǎn)簇系數(shù)的平均復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特征小世界特征（small-worldproperty）無標(biāo)度特征（scale-freeproperty）隨機(jī)網(wǎng)絡(luò)（RandomNetworks）復(fù)雜網(wǎng)絡(luò)（ComplexNetworks）兩個(gè)節(jié)點(diǎn)之間的邊存在與否不再確定，而是根據(jù)一個(gè)概率確定既不是規(guī)則網(wǎng)絡(luò)，也不是隨機(jī)網(wǎng)絡(luò)，而是具有與前兩者皆不同的統(tǒng)計(jì)特征的網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)相關(guān)概念規(guī)則網(wǎng)絡(luò)具有大的簇系數(shù)、大的平均距離隨機(jī)網(wǎng)絡(luò)具有小的簇系數(shù)、小的平均距離大的簇系數(shù)和小的平均距離兩個(gè)統(tǒng)計(jì)特征合在一起稱為小世界效應(yīng)，具有這種效應(yīng)的網(wǎng)絡(luò)就是小世界網(wǎng)絡(luò)在規(guī)則網(wǎng)絡(luò)上以一個(gè)很小的概率添加新的連邊，使得原有的網(wǎng)絡(luò)平均距離縮短真實(shí)網(wǎng)絡(luò)幾乎都具有小世界效應(yīng)復(fù)雜網(wǎng)絡(luò)相關(guān)概念大量真實(shí)網(wǎng)絡(luò)除具有小世界效應(yīng)之外，還具有無標(biāo)度特征節(jié)點(diǎn)度指的是該節(jié)點(diǎn)擁有相鄰節(jié)點(diǎn)的數(shù)目節(jié)點(diǎn)度服從冪律分布是指某個(gè)特定度的節(jié)點(diǎn)數(shù)目與這個(gè)特定的度之間的關(guān)系可以用一個(gè)冪函數(shù)近似表示隨機(jī)網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)的度分布區(qū)間非常窄，幾乎找不到偏離節(jié)點(diǎn)度均值較大的點(diǎn)，故其平均度可看作節(jié)點(diǎn)度的一個(gè)特征標(biāo)度復(fù)雜網(wǎng)絡(luò)的冪律分布是一條下降相對(duì)緩慢的曲線，這使得網(wǎng)絡(luò)中存在度很大的節(jié)點(diǎn)節(jié)點(diǎn)度服從冪律分布的網(wǎng)絡(luò)叫無標(biāo)度網(wǎng)絡(luò)，并稱這種節(jié)點(diǎn)度的冪律分布為網(wǎng)絡(luò)的無標(biāo)度特征鄧巴數(shù)字RobinDunbar認(rèn)為人類社會(huì)網(wǎng)絡(luò)的平均規(guī)模是150Hill,R.A.,andDunbar,R.I.M.Socialnetworksizeinhumans.HumanNature14(2003).數(shù)字和人類工作記憶的容量大小相關(guān)社交=溝通？社會(huì)網(wǎng)絡(luò)分析15社會(huì)網(wǎng)絡(luò)分析不關(guān)注個(gè)體規(guī)范或者獨(dú)立群體的共同活動(dòng)關(guān)注人們的聯(lián)系如何影響他們行動(dòng)中的可能性和限制始于20世紀(jì)30年代，由社會(huì)心理學(xué)家莫雷諾Moreno創(chuàng)立在一個(gè)社會(huì)網(wǎng)絡(luò)中，誰是明星人物？誰是邊緣人物？誰是八卦傳播者，誰是溝通的橋梁？?jī)?nèi)容安排社會(huì)網(wǎng)絡(luò)中心性社會(huì)網(wǎng)絡(luò)的權(quán)威引用社會(huì)網(wǎng)絡(luò)社會(huì)網(wǎng)絡(luò)的鏈接分析社會(huì)網(wǎng)絡(luò)的中心性網(wǎng)絡(luò)中誰更重要發(fā)現(xiàn)名人一個(gè)人在組織中的權(quán)力與他“鑰匙圈上的鑰匙數(shù)量”成反比(ScottAdams)度中心性貼近中心性中介中心性度中心性反映某一個(gè)特定節(jié)點(diǎn)擁有與其他參與者的鏈接或者鏈接數(shù)目在無向圖和有向圖中是不同的在無向圖中，參與者i的度中心性就是i的度與最大度n-1之間的比值在有向圖中，對(duì)于某一個(gè)節(jié)點(diǎn)，主要考慮一個(gè)節(jié)點(diǎn)的鏈出鏈接貼近中心性認(rèn)為一個(gè)參與者如果與其它參與者之間的距離足夠近，這個(gè)參與者就位于中心使用最短距離來度量?jī)蓚€(gè)節(jié)點(diǎn)之間的距離假設(shè)兩個(gè)節(jié)點(diǎn)i和j之間的最短距離為d(i,j)無向圖中，節(jié)點(diǎn)i的貼近中心性的定義為有向圖中，節(jié)點(diǎn)i和j之間的最短距離有時(shí)不存在中介中心性如果兩個(gè)節(jié)點(diǎn)k和j想要彼此聯(lián)系上，而節(jié)點(diǎn)i處在連接它們的路徑上，那么節(jié)點(diǎn)i對(duì)于連結(jié)節(jié)點(diǎn)k和j起到一定的作用對(duì)于節(jié)點(diǎn)i而言，如果它處于更多節(jié)點(diǎn)對(duì)之間的路徑上，那么節(jié)點(diǎn)i對(duì)于其他節(jié)點(diǎn)的控制能力更強(qiáng)，節(jié)點(diǎn)i應(yīng)處于整個(gè)網(wǎng)絡(luò)的中心中介中心性在無向圖中，節(jié)點(diǎn)i的中介中心性定義pjk表示節(jié)點(diǎn)j與節(jié)點(diǎn)k之間的最短路徑數(shù)目，pjk(i)表示節(jié)點(diǎn)j與節(jié)點(diǎn)k之間經(jīng)過節(jié)點(diǎn)i的最短路徑數(shù)目在無向圖中，如果每一對(duì)節(jié)點(diǎn)都滿足上述的理想情況，則節(jié)點(diǎn)i的中介中心性最大歸一化中介中心性節(jié)點(diǎn)i的中介中心性最大中介中心性(3/3)2499:instituteleader2228:chiefdirectorofteachingoffice1126:directorofIT/ISoffice中介中心性有向圖當(dāng)中，依然用類似無向圖中的方式計(jì)算中介中心性節(jié)點(diǎn)k到節(jié)點(diǎn)j最短路徑不同于節(jié)點(diǎn)j到節(jié)點(diǎn)k之間的最短路徑對(duì)于一個(gè)節(jié)點(diǎn)i，歸一計(jì)算結(jié)果為社會(huì)網(wǎng)絡(luò)的權(quán)威在社會(huì)網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)如被大量其它節(jié)點(diǎn)指向，這個(gè)節(jié)點(diǎn)具有非常高的權(quán)威在通過鏈接形成的網(wǎng)頁網(wǎng)絡(luò)中，如果一個(gè)網(wǎng)頁被多個(gè)網(wǎng)頁中的鏈接所指向，那么這個(gè)網(wǎng)頁一定非常具有權(quán)威性權(quán)威與中心性權(quán)威（Prestige）相比于中心性而言，是對(duì)節(jié)點(diǎn)重要性的一個(gè)更加精妙的度量方式權(quán)威只能在有向圖中計(jì)算中心性可以在有向圖和無向圖中計(jì)算權(quán)威則重點(diǎn)考慮一個(gè)節(jié)點(diǎn)的入度中心性只考慮一個(gè)節(jié)點(diǎn)的出度三種常用的權(quán)威性度權(quán)威鄰近權(quán)威等級(jí)權(quán)威度權(quán)威度權(quán)威（DegreePrestige）從一個(gè)節(jié)點(diǎn)度的角度來衡量一個(gè)節(jié)點(diǎn)的權(quán)威如果一個(gè)節(jié)點(diǎn)有多個(gè)鏈入鏈接，這個(gè)節(jié)點(diǎn)一定具有高權(quán)威度量一個(gè)節(jié)點(diǎn)的權(quán)威入度越大，則該節(jié)點(diǎn)的權(quán)威越高鄰近權(quán)威度權(quán)威僅考慮與節(jié)點(diǎn)i相鄰的參與者對(duì)于節(jié)點(diǎn)i，Ii表示能夠到達(dá)該節(jié)點(diǎn)的所有節(jié)點(diǎn)的集合，該集合稱作節(jié)點(diǎn)i的影響區(qū)域用d(j,i)表示節(jié)點(diǎn)j到節(jié)點(diǎn)i的最短路徑長(zhǎng)度，其中每條邊的距離都是1。這樣集合Ii中的平均距離即忽略通過間接的方式依然可以到達(dá)i的節(jié)點(diǎn)鄰近權(quán)威對(duì)于節(jié)點(diǎn)i，影響區(qū)域占全體節(jié)點(diǎn)的比率為：對(duì)于一個(gè)節(jié)點(diǎn)i，如果這個(gè)節(jié)點(diǎn)的影響區(qū)域越大，說明這個(gè)節(jié)點(diǎn)的權(quán)威越高如果節(jié)點(diǎn)i的影響區(qū)域中的節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)i的平均距離越小，則節(jié)點(diǎn)i的權(quán)威也越高。等級(jí)權(quán)威在度權(quán)威和鄰近權(quán)威中，都忽略了其他節(jié)點(diǎn)的權(quán)威如果一個(gè)網(wǎng)頁得到多個(gè)權(quán)威性很高的網(wǎng)頁的指向鏈接，這個(gè)網(wǎng)頁的權(quán)威也會(huì)很高等級(jí)權(quán)威也就是一種考慮了其他節(jié)點(diǎn)的權(quán)威的測(cè)度等級(jí)權(quán)威等級(jí)權(quán)威PR(i)定義為指向節(jié)點(diǎn)i的節(jié)點(diǎn)權(quán)威的線性組合Aji表示節(jié)點(diǎn)j是否指向節(jié)點(diǎn)i。如果節(jié)點(diǎn)j指向節(jié)點(diǎn)i，則Aji=1；否則，Aji=0矩陣A表示網(wǎng)絡(luò)的鄰接矩陣如果有n個(gè)節(jié)點(diǎn)，那么就會(huì)有n個(gè)等式如果j指向i，那么Aji=1；否則Aji=0鏈接模式分析33三元組最基本的鏈接模式閉合三元組核心家庭第三個(gè)節(jié)點(diǎn)的作用提供不同的意見增加反饋渠道A-B-C鏈接模式分析34開放三元組結(jié)構(gòu)洞的作用個(gè)體占據(jù)的結(jié)構(gòu)洞數(shù)量與其作為企業(yè)、銀行、地產(chǎn)代理的業(yè)績(jī)相互關(guān)聯(lián)結(jié)構(gòu)洞禁止進(jìn)入的三元組B的想法A和C的想法維持信息不對(duì)稱跨界套利B為銀行，A公司存款5%，C公司貸款7%RonaldBurst的研究表明，在一個(gè)競(jìng)爭(zhēng)性的市場(chǎng)中，占據(jù)更多結(jié)構(gòu)洞的商人具有更顯著的高成功率引用社會(huì)網(wǎng)絡(luò)社會(huì)網(wǎng)絡(luò)分析另外一個(gè)應(yīng)用領(lǐng)域是科技文獻(xiàn)之間的引用分析(CitationAnalysis)每一篇學(xué)術(shù)文章引用不同作者的文獻(xiàn)，引用讓學(xué)術(shù)文章之間構(gòu)成了聯(lián)系，形成網(wǎng)絡(luò)同引分析(Co-Citation)引文耦合(BibliographicCoupling)同引分析在科技文獻(xiàn)之間，經(jīng)常存在兩篇論文i和j同時(shí)被一篇論文k引用的情況同引分析就是利用這樣的一種關(guān)系來度量論文i和j之間的相似程度同引分析假設(shè)有n篇論文，L為其引用矩陣引用矩陣L中的第i行第j列的元素Lij表明兩篇論文i和j之間的引用關(guān)系如果論文i中引用了論文j，則Lij=1論文i沒有引用論文j，則Lij=0同時(shí)引用論文i和j的論文數(shù)Cij引文耦合在引文耦合中，如果計(jì)算同時(shí)被論文i和論文j引用的論文數(shù)社會(huì)網(wǎng)絡(luò)中的鏈接分析社會(huì)網(wǎng)絡(luò)的鏈接分析中經(jīng)典方法PageRank算法1998年提出GoogleHITS算法1999年提出PageRank&

網(wǎng)頁排名PageRank是由谷歌創(chuàng)始人SergeyBrin和LawrencePage提出，它的成功很大程度要?dú)w功于谷歌的商業(yè)成功PageRank的經(jīng)典應(yīng)用：網(wǎng)頁排名一種靜態(tài)的網(wǎng)頁評(píng)級(jí)算法為每個(gè)網(wǎng)頁離線計(jì)算PageRank值而且該值與查詢內(nèi)容無關(guān)。PageRank算法依賴于Web的自然特性，它利用Web的龐大鏈接結(jié)構(gòu)來作為單個(gè)網(wǎng)頁質(zhì)量的參考。PageRank將網(wǎng)頁之間按照鏈接的方式組成一個(gè)網(wǎng)絡(luò)從其他網(wǎng)頁指向網(wǎng)頁i的鏈接。不考慮來自同一網(wǎng)站的鏈接每個(gè)網(wǎng)頁的PageRank值就可以看做該網(wǎng)頁的權(quán)威值網(wǎng)頁i的鏈入鏈接從網(wǎng)頁i指向其他網(wǎng)頁的鏈接。也不考慮來自同一網(wǎng)站的鏈接網(wǎng)頁i的鏈出鏈接PageRankPageRank算法基于如下三點(diǎn)假設(shè)如果一個(gè)頁面被很多其他頁面所指向，則這個(gè)頁面可能是重要的如果一個(gè)頁面被重要的頁面所指向，則這個(gè)頁面可能是重要的一個(gè)頁面的重要性均分傳播到它指向的頁面中PageRank給定4個(gè)網(wǎng)頁所組成的文檔集合{A,B,C,D}轉(zhuǎn)置矩陣M中每一個(gè)元素表示相應(yīng)的列的網(wǎng)頁轉(zhuǎn)移到相應(yīng)行的網(wǎng)頁的概率轉(zhuǎn)移矩陣的轉(zhuǎn)置矩陣PageRank轉(zhuǎn)置矩陣M，Mjk是M中第j行第k列的元素，其取值分為兩種情況若節(jié)點(diǎn)k和節(jié)點(diǎn)j之間存在k指向j的邊|O(k)|表示節(jié)點(diǎn)k的出度，也就是鏈出鏈接的個(gè)數(shù)若兩個(gè)節(jié)點(diǎn)之間不存在k指向j的邊，則相應(yīng)的Mjk=0任意節(jié)點(diǎn)j的權(quán)威度可按照如下的方法計(jì)算：PageRank權(quán)威度的定義采用遞歸的方式，因此可以進(jìn)行迭代計(jì)算每個(gè)節(jié)點(diǎn)的權(quán)威度為1/n，也就是R0(j)=1/n將所有節(jié)點(diǎn)權(quán)威度構(gòu)成一個(gè)向量R，可利用矩陣運(yùn)算的方法對(duì)R進(jìn)行迭代PageRank為了使此迭代計(jì)算收斂，矩陣M滿足要求：M必須不可約(強(qiáng)連通圖)，M中任何兩個(gè)節(jié)點(diǎn)都可達(dá)在圖G中為每個(gè)節(jié)點(diǎn)增加n條邊，指向圖中的每一個(gè)節(jié)點(diǎn)，包括自己本身，這樣形成一個(gè)新的圖G*PageRank改變后的矩陣用M*表示，則新的迭代公式如下所示如果給定初始狀態(tài)下的權(quán)威度為R0=(0.25,0.25,0.25,0.25)TC=0.8按迭代計(jì)算公式得到4個(gè)網(wǎng)頁的權(quán)威度結(jié)果為R=(0.176,0.176,0.332,0.316)T四個(gè)網(wǎng)頁的排名結(jié)果為<CDAB>PageRank優(yōu)點(diǎn)防止作弊的發(fā)生一個(gè)頁面的權(quán)威和重要性是由指向它的頁面所決定的，也就是由該頁面的鏈入鏈接決定在用戶進(jìn)行檢索時(shí)，搜索的效率就非常高每一個(gè)頁面的PageRank值不受查詢條件的影響，它只受全局的鏈接情況影響所有頁面的PageRank值都是在離線的情況下計(jì)算出來的，而不是在用戶查詢時(shí)計(jì)算的PageRank不足PageRank值與查詢條件無關(guān)的這一特點(diǎn)也會(huì)導(dǎo)致一些缺陷用戶在查詢某一個(gè)特定話題時(shí)，往往希望得到僅在這一話題上的權(quán)威頁面，而PageRank所給出的是廣泛意義上的權(quán)威PageRank算法也沒有考慮頁面的生成時(shí)間，它將新舊頁面統(tǒng)一對(duì)待針對(duì)這一不足，已有很多研究人員提出了考慮時(shí)間的PageRank算法（TimedPageRank）HITSHITS算法是英文HypertextInducedTopicSearch首字母縮寫HITS算法是與查詢相關(guān)的當(dāng)用戶提交一個(gè)查詢請(qǐng)求時(shí)，HITS算法首先得到檢索系統(tǒng)返回的相關(guān)頁面，并依此為基礎(chǔ)，從鏈入鏈接和鏈出鏈接兩個(gè)角度擴(kuò)展出兩個(gè)頁面集合，并計(jì)算頁面的評(píng)級(jí)權(quán)威等級(jí)（Authorityranking）中心等級(jí)（Hubranking）HITS權(quán)威網(wǎng)頁和中心網(wǎng)頁一個(gè)有權(quán)威（Authority）的網(wǎng)頁，意味著這個(gè)網(wǎng)頁一定擁有數(shù)量眾多的鏈入鏈接。有權(quán)威的網(wǎng)頁會(huì)包含重要或者權(quán)威的信息，會(huì)得到許多外部網(wǎng)頁的信賴和引用一個(gè)中心（Hub）的網(wǎng)頁，意味著這個(gè)網(wǎng)頁一定擁有數(shù)量眾多的鏈出鏈接，這些鏈接分別指向不同的權(quán)威網(wǎng)頁。一個(gè)中心網(wǎng)頁作為某個(gè)特定話題的組織和集成者，它會(huì)指向許多和這個(gè)話題相關(guān)的權(quán)威網(wǎng)頁。HITSHITS算法的核心思想是中心網(wǎng)頁和權(quán)威網(wǎng)頁之間存在互相促進(jìn)的關(guān)系好的中心網(wǎng)頁一定會(huì)有很多的鏈出鏈接指向好的權(quán)威網(wǎng)頁好的權(quán)威網(wǎng)頁也一定會(huì)包含很多好的中心網(wǎng)頁的鏈入鏈接HITS當(dāng)用戶提交查詢條件q之后，檢索系統(tǒng)會(huì)檢索到相關(guān)網(wǎng)頁，并根據(jù)網(wǎng)頁的相關(guān)性將檢索結(jié)果排序。HITS算法一般選取排名在前200的網(wǎng)頁，這些網(wǎng)頁與查詢條件