商務(wù)智能原理與方法（第3版）-課件 Lecture7-Social Network

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

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