Web信息處理與應(yīng)用復(fù)習(xí)筆記-GitHub

1、Web信息處理與應(yīng)用復(fù)習(xí)筆記? 2017-1 熊家靖 PB14011026PART 1：Web Search一、 Introduction1、 web 搜索的挑戰(zhàn)：數(shù)據(jù)規(guī)模大、分布散、不穩(wěn)定、質(zhì)量差、無結(jié)構(gòu)、異構(gòu)、價值低2、信息檢索：給定查詢和信息庫，找到相關(guān)的文檔3、 IR 與 DB 的區(qū)別：DB 數(shù)據(jù)結(jié)構(gòu)化、有明確語義，查詢結(jié)構(gòu)化、匹配要精確、次序不重要IR 數(shù)據(jù)半結(jié)構(gòu)化、無明確語義，查詢?yōu)槿我鈨?nèi)容、無需精確匹配、次序很重要4、 IR 的任務(wù)：基于用戶查詢的搜索、信息過濾、分類、問答5、 IR 的基礎(chǔ)性問題：相關(guān)性計算、檢索模型、評價、信息需求、檢索性能二、 Web Crawler1、網(wǎng)絡(luò)

2、爬蟲的概念：從一個種子站點集合開始，從web 中尋找并且下載網(wǎng)頁，獲取排序需要的相關(guān)信息，并且剔除低質(zhì)量的網(wǎng)頁2、網(wǎng)絡(luò)爬蟲基本過程：種子裝入桶中、每次從桶中取出一個網(wǎng)頁、提取出網(wǎng)頁所有url 放入桶中、重復(fù)3、網(wǎng)絡(luò)爬蟲的主要需求：快、可擴(kuò)展性、友好性、健壯、持續(xù)搜集、時新性4、網(wǎng)絡(luò)爬蟲的常用策略：用棧深度優(yōu)先、用隊列廣度優(yōu)先5、網(wǎng)絡(luò)爬蟲涉及的協(xié)議：HTTP/HTML、 DNS/URL、 Robots Exclusion（排斥協(xié)議）、 Sitemp（允許協(xié)議）6、 URL 規(guī)范化：協(xié)議 :/ 主機(jī)名 :端口 / 路徑 /: 參數(shù) ?查詢 #Fragment7、分布式爬蟲的概念：如何有效地把N 個

3、網(wǎng)站的搜集任務(wù)分配到M 個機(jī)器上去使得分配比較均勻8、一致性Hash 的概念：將網(wǎng)頁和機(jī)器都映射到環(huán)路 Hash 空間，每個機(jī)器負(fù)責(zé)自身位置與后繼的網(wǎng)頁搜集三、 Text Processing1、文本處理的概念：將原始文檔轉(zhuǎn)換成詞項集以方便索引2、字符編碼的概念：ASCII：美國信息交換標(biāo)準(zhǔn)代碼Unicode： 統(tǒng)一碼，滿足跨語言、跨平臺的需求UTF-8 ：針對Unicode的可變長度字符編碼3、分詞中的概念：- 1 -分詞：將文檔的字符串序列變成詞序列語素：最小的語音語義結(jié)合體，是最小的語言單位詞：代表一定的意義，具有固定的語音形式，可以獨(dú)立運(yùn)用的最小的語言單位交叉歧義：網(wǎng)球 /場 / 網(wǎng)

4、/球場 /組合歧義：我/ 個人 /三 /個 /人 /未登錄詞： 未包括在分詞詞表中但必須切分出來的詞，包括各類專名、術(shù)語、 縮略語等停用詞：在文檔中頻繁出現(xiàn)或與語料庫特性有關(guān)的詞4、中文分詞的挑戰(zhàn)：漢語是字的集合而不是詞的集合漢字存在著不同的組詞方式漢語虛詞眾多，大多數(shù)漢字在不同的詞語中可能為關(guān)鍵字，也可能為停用詞分詞歧義新詞的頻繁出現(xiàn)5、常用的分詞方法：機(jī)械分詞：正向最大匹配分詞FMM反向最大匹配分詞BMM / RMM雙向最大匹配分詞BM: FMM + RMM最少切分分詞：圖中最短路徑ASM( d, a, m ) d為匹配方向，a 為失敗后增/減串長， m 為最大 /小匹配理解分詞：分詞時進(jìn)

5、行句法、語義分析，從而減少歧義統(tǒng)計分詞：一元文法模型即最大概率分詞二元文法模型每個詞的概率為前一個詞出現(xiàn)后的條件概率N 元文法模型每個詞的概率為前N 個詞出現(xiàn)后的條件概率6、詞根化和編輯距離的概念：詞根化：使用一系列后綴變換規(guī)則對單詞進(jìn)行變換編輯距離：從s 轉(zhuǎn)換為 t 使用增加、刪除、替換三種操作的最小次數(shù)四、 Indexing1、布爾檢索的概念：利用 AND 、 OR 或者 NOT 操作符將詞項連接起來的查詢2、關(guān)聯(lián)矩陣的概念：行為詞項，列為文檔，詞項在文檔中出現(xiàn)為1 不出現(xiàn)為03、倒排索引的概念和結(jié)構(gòu)：以詞項為索引，每個詞項維護(hù)一個鏈表，表示其出現(xiàn)過的文檔集（從小到大）可以加入擴(kuò)展項：某詞

6、在某文檔中的出現(xiàn)詞頻TF 、某詞出現(xiàn)過的文檔頻數(shù)DF4、倒排索引的構(gòu)建：寫出每個文檔的詞項-> 文檔索引合并所有的索引，詞項和文檔號均從小到大排列5、倒排索引的存儲：詞項與鏈表存儲在同一個文件中/不同文件中6、詞匯表存儲結(jié)構(gòu)：順序存儲、 Hash table、 B+- 樹、 Trie 樹7、 Zipf Law：任意一個詞項，其頻度和排名的乘積大致是一個常數(shù)- 2 -五、 Queries1、查詢表達(dá)的難點：一個查詢可以代表非常不同的信息需求一個查詢可能是其真正需求的一種非常差的表述2、查詢表達(dá)的優(yōu)化：局部優(yōu)化：對用戶查詢進(jìn)行局部分析，如相關(guān)性反饋全局優(yōu)化：進(jìn)行全局分析來產(chǎn)生同/ 近義詞詞典

7、，如查詢擴(kuò)展3、相關(guān)性反饋的概念和過程：用戶在查詢后標(biāo)記相關(guān)/不相關(guān)文檔，然后迭代更新查詢以獲得更好的結(jié)果4、相關(guān)性反饋的分類及其各自的概念和特點：顯式反饋：定義：用戶顯式參加交互過程，即用戶反饋問題：開銷大、查詢長、用戶不愿意、反饋邏輯難理解隱式反饋：定義：系統(tǒng)跟蹤用戶的行為來推測返回文檔的相關(guān)性，從而反饋好處：省卻了用戶的顯式參與過程問題：對分析的要求高、準(zhǔn)確度難保證、可能需要額外設(shè)備偽相關(guān)反饋： 定義：對于真實相關(guān)反饋的人工部分進(jìn)行自動化好處：不用考慮用戶因素，處理簡單，平均效果也不錯問題：準(zhǔn)確率難以保證，可能出現(xiàn)查詢漂移5、 Ricchio算法：新查詢向量= ·原查詢向量+

8、·平均相關(guān)向量·平均不相關(guān)向量計算過程中出現(xiàn)負(fù)值，全部設(shè)為0基本假設(shè)：用戶知道使用文檔集中的詞項來表達(dá)初始查詢；相關(guān)文檔出現(xiàn)的詞項類似6、查詢擴(kuò)展的概念：相關(guān)性反饋中，用戶針對文檔提供附加信息，查詢擴(kuò)展中，用戶對詞項提供附加信息7、查詢擴(kuò)展的幾種方法：人工構(gòu)建同 / 近義詞詞典、自動導(dǎo)出同 /近義詞詞典、基于查詢?nèi)罩就诰虿樵兊葍r類六、 Ranking1、 Ranking的難點：Web 網(wǎng)頁的質(zhì)量參差不齊，大量的網(wǎng)頁組織性、結(jié)構(gòu)性比較差大部分檢索用戶是沒有任何經(jīng)驗的用戶的查詢需求存在著巨大差異2、信息檢索模型的概念：用來描述文檔和用戶查詢的標(biāo)識形式以及它們之間相關(guān)性的框架形式

9、化表示為： D, Q, F, R(Di,q) 即 文檔表達(dá) , 查詢表達(dá) , 匹配框架 , 相關(guān)性度量函數(shù)3、信息檢索的實質(zhì)問題：對于所有文檔，根據(jù)其與用戶查詢的相關(guān)程度從大到小排序4、信息檢索模型與搜索引擎排序算法的關(guān)系：好的信息檢索模型在相關(guān)性上產(chǎn)生和人類決策非常相關(guān)的結(jié)果基于好的檢索模型的排序算法能夠在排序結(jié)果頂部返回相關(guān)的文檔5、信息檢索的分類：基于集合論的模型：布爾模型基于代數(shù)論的模型：向量空間模型基于概率論的模型：概率模型、語言模型、推理網(wǎng)絡(luò)6、相關(guān)系數(shù)的概念和計算：- 3 -Jaccard ： A 與 B 的交中元素的個數(shù)/A 與 B 的并中元素的個數(shù)# 未考慮詞頻、文檔長度、罕

10、見詞信息量tf( t, d ) ： 詞項 t 在文檔d 中出現(xiàn)的次數(shù)# 相關(guān)度不會正比于詞項頻率w( t, d ):當(dāng) tf > 0 時， 1 + lg( tf ) ； 否則， 0df( t ):出現(xiàn)詞項 t 的文檔數(shù)目idf( t ):lg( N / df )其中 N 是文檔集中文檔的數(shù)目tf-idf:( 1 + lg tf )lg( N·/ df )# 隨著詞項頻率的增大而增大# 隨著詞項罕見度的增大而增大7、向量空間模型SMART ：D： 每個文檔是一個以詞項為維度的向量，每個維度的值為詞項的tf-idf 值Q： 每個查詢是一個以詞項為維度的向量，每個維度的值為詞項的tf

11、-idf 值F ： 非完全匹配R： 用文檔向量和查詢向量的相似度來估計相關(guān)性前提假設(shè)：檢索到的所有文檔相關(guān)性不等價、相關(guān)性多元、查詢關(guān)鍵字互相獨(dú)立8、余弦相似度：兩個向量夾角的余弦值，即：兩向量的點乘/ 各自模的積9、向量空間模型的操作過程：文檔和查詢表示成tf-idf 的權(quán)重向量計算兩向量余弦相似度將余弦相似度Top-K 的文檔返回給用戶10 、向量空間模型的缺點：用戶無法描述詞項之間的關(guān)系tf-idf 高的詞項可能會在檢索中影響過大詞項之間的獨(dú)立性假設(shè)與實際不符11 、概率模型：定義隨機(jī)變量R、Q、D，相關(guān)度R=0 或 1通過計算條件概率P( R = 1 | Q = q, D = d )來

12、度量文檔和查詢的相關(guān)度12 、 PageRank：PR(a) = ( 1d ) + dsigma(· PR(T) / C(T) )每個頁面的pagerank等于進(jìn)入它的邊的pagerank的函數(shù)計算過程：每個網(wǎng)頁賦初值，然后迭代計算，直到變化小于一個閾值優(yōu)點：給網(wǎng)頁提供重要性排序+ 可以離線完成+ 獨(dú)立于主題缺點：未區(qū)分鏈接種類+ 對新網(wǎng)頁不公平+ 不能單獨(dú)用于排序13 、 HITS ：入步驟：所有權(quán)威頁面的值等于鏈向它的中心頁面的值之和出步驟：所有中心頁面的值等于其鏈向的權(quán)威頁面的值之和計算過程：所有頁面初始為1 ，迭代使用入步驟和出步驟優(yōu)點：能更好描述互聯(lián)網(wǎng)的組織特點+ 主題相關(guān)

13、+ 查詢無關(guān)+ 可以單獨(dú)用于排序缺點：需要在線計算時間代價大+ 容易受到“鏈接作弊”的影響七、 Evaluation1、信息檢索評價概述：評價受主觀、情景、認(rèn)知、時間的影響，重點在于保持公平- 4 -2、信息檢索評價指標(biāo)：效率：時間開銷、空間開銷、響應(yīng)速度效果：準(zhǔn)確率、召回率、是否靠前其他：覆蓋率、訪問量、數(shù)據(jù)更新速度3、效果評價指標(biāo)：基于集合：正確率 P ：返回的相關(guān)文檔占返回的總文檔的比比例召回率 R：返回的相關(guān)文檔占相關(guān)總文檔的比例F 值：召回率 R 和正確率 P 的調(diào)和平均F值：召回率 R 和正確率 P 的加權(quán)調(diào)和平均其中 R 的權(quán)為 2 ， P 的權(quán)為 1基于序：PN ：值考慮返回的

14、前 N 個文檔時的正確率R-Precision ： 即 P 相關(guān)文檔總數(shù)未插值 AP ：P 相關(guān)文檔出現(xiàn)位置的平均插值 AP：在召回率 0,0.1,0.21.0 上十一點的正確率平均不存在某召回率點時， 取該點到下一個點之間最大正確率簡化 AP：在未插值 AP 中忽略未出現(xiàn)的相關(guān)文檔多個查詢：MAP ：所有查詢的 AP 的算術(shù)平均MRR ：第一個相關(guān)文檔返回的位置的倒數(shù)的算術(shù)平均其他：CGp ：位置 1 到位置 p 的檢索結(jié)果的相關(guān)度之和DCGp ：相關(guān)度要先除以 log2(i) 作為懲罰，其中 i 為出現(xiàn)的位置NDCGp ：DCG 的值除以理想化的 IDCG 的值，規(guī)范化為 0,1PART

15、2：Web Information Extraction一、 Named Entity Extraction1、信息抽取的概念：從語料中抽取指定的事件、事實等信息，形成結(jié)構(gòu)化的數(shù)據(jù)能作為一種淺層的文本理解，是信息檢索的進(jìn)一步深化2、信息抽取與信息檢索的關(guān)系：檢索是從文檔集合中找文檔子集，抽取是從文本中獲取用戶感興趣的事實信息檢索通常利用統(tǒng)計與關(guān)鍵詞等技術(shù)，抽取借助于自然語言處理技術(shù)檢索通常與領(lǐng)域無關(guān)，抽取通常與領(lǐng)域相關(guān)3、 MUC-7 定義的信息抽取任務(wù)：命名實體 NE：現(xiàn)實世界中具體或抽象的實體，還包括日期、時間、數(shù)量等模板元素 TE：實體屬性，通過槽描述命名實體的基本信息共指關(guān)系CR：命名

16、實體的等價關(guān)系模板關(guān)系TR：實體之間的各種關(guān)系，又稱為事實背景模板ST：實體發(fā)生的事件4、信息抽取的內(nèi)容：實體、屬性、關(guān)系、事件關(guān)鍵在于“抽取實體，確定關(guān)系”5、命名實體識別NER的概念：識別文本中的人名、地名等專有名稱和有意義的時間、日期等數(shù)量短語并加以歸類6、命名實體識別NER的難點：命名實體類型多樣、新命名實體不斷出現(xiàn)、命名實體歧義、命名實體結(jié)構(gòu)復(fù)雜- 5 -7、 MUC-7 中定義的NER內(nèi)容：實體類：人名、地名、機(jī)構(gòu)名時間類：日期、時間數(shù)值類：貨幣、百分比注意：人造物、重復(fù)指代的普通名詞、派生詞、以人命名的法律和獎項等不算！8、命名實體識別NER的性能評價指標(biāo)：正確率 P：正確數(shù)/

17、總數(shù)( 正確數(shù)+ (1/2) 部分正確數(shù)) / 總數(shù)召回率 R：正確數(shù)/ 總正確數(shù)( 正確數(shù)+ (1/2) 部分正確數(shù)) / 總 (部分 )正確數(shù)F 值：P與 R 的調(diào)和平均9、命名實體識別NER的常用方法：基于詞典：詞典匹配；難以枚舉命名實體、構(gòu)建詞典代價大、難以處理歧義基于規(guī)則：自行構(gòu)造模板匹配；依賴性強(qiáng)、代價大、建設(shè)周期長、可移植性差基于統(tǒng)計：隱馬爾可夫HMM 、最大熵ME、支持向量機(jī)SVM、條件隨機(jī)場CRF混合方法：混合使用詞典、規(guī)則和統(tǒng)計二、 Relation Extraction1、關(guān)系抽取的概念：從文本中識別出兩個實體或多個實體之間存在的事實上的關(guān)系2、關(guān)系抽取的意義：提高搜索引

18、擎發(fā)現(xiàn)知識的能力廣泛應(yīng)用于各種知識庫的構(gòu)建支持知識推理和問答系統(tǒng)研究3、關(guān)系的表示方法：二元組、三元組、多元組4、關(guān)系抽取的常用方法：基于規(guī)則：針對特定領(lǐng)域的特定關(guān)系，設(shè)計針對性的抽取規(guī)則，代價大，難移植基于模式： 種子關(guān)系生成關(guān)系模式，基于關(guān)系模式抽取新的關(guān)系，再迭代生成新的模式和新的關(guān)系基于機(jī)器學(xué)習(xí)：特征向量、核函數(shù)5、 DIPRE系統(tǒng)：給定種子元組R在文檔中搜索元組R 的出現(xiàn) O從出現(xiàn) O 中提取模板P使用模板P 從文檔中獲取新的元組6、 Snowball 系統(tǒng)：只使用能匹配很多模板的元組只使用有多個元組支持的模板PART 3： Web Data Mining一、 Introductio

19、n1、網(wǎng)絡(luò)挖掘的概念：從 web 中挖掘有用的信息和有用的模式2、網(wǎng)絡(luò)挖掘的內(nèi)容與應(yīng)用：網(wǎng)絡(luò)內(nèi)容挖掘：數(shù)據(jù)挖掘、數(shù)據(jù)分類、數(shù)據(jù)聚類網(wǎng)絡(luò)結(jié)構(gòu)挖掘：社區(qū)分析、影響力分析- 6 -網(wǎng)絡(luò)用途挖掘：推薦系統(tǒng)二、 Data1、數(shù)據(jù)對象、屬性、維度、特征：數(shù)據(jù)對象是一個數(shù)據(jù)實例，其屬性、維度、 特征意思相同， 均為描述數(shù)據(jù)的一個域2、高維詛咒現(xiàn)象：數(shù)據(jù)分類的表現(xiàn)不會隨著維數(shù)的增加而一直上升，反而到了某個閾值后會下降因為隨著維數(shù)上升，每個類的數(shù)據(jù)變得稀疏，很多測量手段都逐漸失去意義3、數(shù)據(jù)預(yù)處理的基本方法：采樣：使用有代表性的樣本，使得樣本與總體在屬性上有相似的性質(zhì)特征選擇：剔除冗余和無關(guān)特征降維：避免高維詛

20、咒、降低數(shù)據(jù)挖掘的代價、使數(shù)據(jù)更加清楚、消除噪聲三、 Classification1、監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)：監(jiān)督學(xué)習(xí)：使用訓(xùn)練樣本訓(xùn)練模型，再利用模型解析未知數(shù)據(jù)進(jìn)行分類無監(jiān)督學(xué)習(xí)：無訓(xùn)練樣本，直接按照未知數(shù)據(jù)的相似程度建模聚類2、分類的基本原理：選定模型后，使用訓(xùn)練數(shù)據(jù)訓(xùn)練模型參數(shù)，之后用模型解析輸入數(shù)據(jù)得到分類3、數(shù)據(jù)的向量表示：用數(shù)據(jù)的頻數(shù)或者tf-idf 表示4、 KNN 算法：找到與待分類數(shù)據(jù)距離最近的K 個數(shù)據(jù)，然后將其分入頻數(shù)最高的類中KNN 無法免疫高維詛咒現(xiàn)象，但是在高維特征獨(dú)立數(shù)較小時，KNN 也適用5、 Logistic regression 算法：6、如何評價分類效果：

21、訓(xùn)練誤差：訓(xùn)練數(shù)據(jù)的過程中造成的錯誤測試誤差：測試的過程中造成的誤差accuracy 為測準(zhǔn)率泛化誤差：使用模型在未知記錄上造成的分布相同的期望誤差四、 Clustering1、聚類的概念：聚類是一個把現(xiàn)實或抽象的對象和與它相似的對象組織到一起的過程2、聚類的基本原理：聚類內(nèi)部相似性很高，聚類之間相似性很低3、層次式聚類算法流程：計算距離矩陣，默認(rèn)所有數(shù)據(jù)點都是一個類每次找到距離最近的兩個類，將其合并，并更新距離矩陣，重復(fù)直到只有一個類4、類的距離定義：Single-link：使用兩個聚類之間最近的點作為聚類的距離Complete-link ：使用兩個聚類之間最遠(yuǎn)的點作為聚類的距離Averag

22、e-link ：使用所有跨聚類的結(jié)點對的平均距離Centroid ：使用聚類重心之間的距離5、 K-means 算法流程：隨機(jī)產(chǎn)生k 個聚類中心點每個數(shù)據(jù)點歸類到與它最近的那個中心所代表的類- 7 -每個類重新計算中心點，返回第二步算法迭代到所有數(shù)據(jù)點的類歸屬不再改變6、 K-means 算法優(yōu)化目標(biāo)：每個數(shù)據(jù)點到它所屬的類中心距離的平方和最小7、 K-means 收斂性分析：均方差函數(shù)單調(diào)遞減而有界8、聚類算法的評價標(biāo)準(zhǔn)：凝聚度：計算各聚類的均方差的和分離度：不同聚類的重心要盡可能相互遠(yuǎn)離專家評判五、社區(qū)分析：1、圖的表示、組成部分以及相關(guān)性質(zhì)：點、邊（有向、無向）2、社區(qū)的概念：一組結(jié)點集

23、，集合內(nèi)的點之間有很多聯(lián)系，而集合內(nèi)的點與集合外的點聯(lián)系很少3、社區(qū)發(fā)現(xiàn)與聚類：基于結(jié)構(gòu)相似性通過使用層次式聚類或分割式聚類4、結(jié)構(gòu)相似度計算：結(jié)構(gòu)差異測度dij ：取兩點關(guān)聯(lián)向量的差，向量中兩點所在的位置清零，取模Jaccard相似度：兩點公共鄰居數(shù)/ 兩點無重總鄰居數(shù)余弦相似度：兩點關(guān)聯(lián)向量的余弦5、 GN 算法：一對結(jié)點之間的最短路徑為路上的邊貢獻(xiàn)一個流若最短路徑有多條，則均分每次切除一條流量最大的邊，然后重新計算流量，迭代進(jìn)行，直到無邊6、矩陣及性質(zhì)：鄰接矩陣：相鄰為1，不相鄰為0度數(shù)矩陣：對角線放每個結(jié)點的度數(shù)，其余地方為0拉普拉斯矩陣：度數(shù)矩陣減去鄰接矩陣，是半正定的7、 Cut

24、的性質(zhì)：Cut( A, B )表示 A 與 B 之間的邊數(shù)1?1?Cut( A, B ) = 4 ?( ?-?) ?= 4 ? ?；當(dāng) u A， y(u) = 1，當(dāng) u B， y(u) = -111RatioCut ( A,B) = cut(A, B)( |?| + |?|)NCut( A,B) =cut(A, B)(11)vol(A)表示 A 中結(jié)點度數(shù)之和+?(?)?(?)? ( ?-? )?RatioCut ( A,B) = ? ?st. ?= 0? -0.5-0.5?()?(?-? ) ? 0.5NCutA,B=?st. ? ?= 0?8、 modularity的概念：一種測量網(wǎng)絡(luò)劃

25、分為社區(qū)的好壞程度的指標(biāo)?，期望邊數(shù)為? ? ?兩結(jié)點間的實際邊數(shù)為，每個社區(qū)內(nèi)的邊數(shù)差為?2?- 2?- 8 -每個社區(qū)內(nèi)邊數(shù)差相加后除以總度數(shù)2m，即為 Q( G, S 屬)于 -1, 1六、影響力分析：1、度量結(jié)點中心性的標(biāo)準(zhǔn)：Degree centrality ：結(jié)點的度，可以除以n-1 標(biāo)準(zhǔn)化Closeness centrality：結(jié)點到其他結(jié)點的平均測地距離的倒數(shù)Betweenness centrality ：該結(jié)點通過的流量，可除以(n-1)(n-2)/2 標(biāo)準(zhǔn)化Eigenvector centrality ： Ax = x，其中 x 是所有結(jié)點的Eigenvector cen

26、trality2、關(guān)系強(qiáng)度：刪除后會造成結(jié)點對不連通的邊叫橋刪除后造成的結(jié)點對的距離增量越大，該關(guān)系越不牢固鄰居 overlap 函數(shù)：兩結(jié)點公共鄰居數(shù)/ ( 兩結(jié)點無重總鄰居數(shù)2 )s3、影響力傳播模型：線性閾值模型LTM：關(guān)聯(lián)到某結(jié)點的激發(fā)邊的總激發(fā)值大于閾值，則該結(jié)點被激發(fā)層級傳播模型ICM：激發(fā)結(jié)點按照邊權(quán)概率激發(fā)周圍的結(jié)點區(qū)別： LTM 是基于接收者的，ICM 是基于發(fā)送者的LTM 依賴于所有鄰居結(jié)點，ICM 影響到所有鄰居結(jié)點LTM 狀態(tài)只依賴于閾值，ICM 的狀態(tài)存在隨機(jī)性但是他們都具有子模性質(zhì)！4、最大影響結(jié)點集：f(S)是結(jié)點集S 最終能夠影響的結(jié)點集的大小最優(yōu)化問題： max