雙網(wǎng)絡(luò)中影響力凝聚子圖發(fā)現(xiàn)算法

李 源 楊 森 孫 晶 趙會(huì)群 王國仁

1（北方工業(yè)大學(xué)信息學(xué)院 北京 100144）

2（北京理工大學(xué)計(jì)算機(jī)學(xué)院 北京 100081）

（liyuan@ncut.edu.cn）

隨著社交媒體、在線社區(qū)和移動(dòng)通信等信息技術(shù)的快速發(fā)展，這些數(shù)據(jù)實(shí)體積累了大量的數(shù)據(jù)重復(fù)關(guān)系[1].鑒于圖模型簡單而強(qiáng)大的表達(dá)能力，這些數(shù)據(jù)通常被建模為圖，圖中的結(jié)點(diǎn)表示實(shí)體，結(jié)點(diǎn)之間的邊表示實(shí)體間的關(guān)系.從全局角度看，真實(shí)圖往往都是稀疏圖，但又包含局部關(guān)系緊密連接的凝聚子圖[2-3]，這些凝聚子圖中往往包含著人們需要的重要信息.由于大規(guī)模真實(shí)網(wǎng)絡(luò)中凝聚子圖數(shù)量眾多，因此尋找具有影響力（重要性）的凝聚子圖成為當(dāng)前的熱點(diǎn)問題，有重要現(xiàn)實(shí)意義[4-9].目前，許多影響力圖模型已經(jīng)被提出.首先，針對(duì)圖中單個(gè)影響力結(jié)點(diǎn)，MIPPLA 模型[10]和EDBC 模型[11]被提出.隨后，文獻(xiàn)[12-16]提出不同算法用于發(fā)現(xiàn)圖中影響力凝聚子圖.但文獻(xiàn)[12-16]所提算法往往僅限于解決單網(wǎng)絡(luò)中影響力凝聚子圖計(jì)算問題.

隨著應(yīng)用場(chǎng)景愈發(fā)豐富，實(shí)體間的關(guān)系也變得愈發(fā)復(fù)雜，單個(gè)網(wǎng)絡(luò)的表達(dá)能力已經(jīng)不能滿足需求.對(duì)此，Wu 等人[17]提出了一種雙網(wǎng)絡(luò)模型.雙網(wǎng)絡(luò)表示為2 個(gè)互補(bǔ)的單網(wǎng)絡(luò)，這2 個(gè)單網(wǎng)絡(luò)包含相同的結(jié)點(diǎn)集合和不同的邊集合.其中一個(gè)網(wǎng)絡(luò)表示結(jié)點(diǎn)之間真實(shí)存在的物理關(guān)系，如同事、朋友、家人等，該圖稱作物理圖；另一個(gè)網(wǎng)絡(luò)表示結(jié)點(diǎn)之間的概念關(guān)系，如相似、喜好程度等通過一些度量函數(shù)計(jì)算得來的關(guān)系，該圖稱作概念圖.因此，雙網(wǎng)絡(luò)中的物理圖可表示為不帶邊權(quán)重的無向圖，而概念圖可表示為帶邊權(quán)重的無向圖.值得注意的是，子圖權(quán)重能夠有效表達(dá)子圖在網(wǎng)絡(luò)中的影響力.本文聚焦于發(fā)現(xiàn)概念圖中影響力大且稠密同時(shí)物理圖內(nèi)連通的子圖.該問題在利用研究者雙網(wǎng)絡(luò)進(jìn)行研討會(huì)籌備、社交雙網(wǎng)絡(luò)進(jìn)行商品推薦和生物雙網(wǎng)絡(luò)進(jìn)行致病基因發(fā)現(xiàn)等真實(shí)場(chǎng)景中具有廣泛應(yīng)用.

圖1 展示了利用研究者雙網(wǎng)絡(luò)進(jìn)行研討會(huì)籌備的案例.當(dāng)前的需求是尋找一組研究興趣相似又彼此認(rèn)識(shí)的研究人員參加研討會(huì).圖1（a）為研究者雙網(wǎng)絡(luò)的物理圖，結(jié)點(diǎn)之間存在邊表示研究者之間合作發(fā)表過若干篇論文；圖1（b）為概念圖，邊上的權(quán)重表示研究者之間研究興趣的相似度.從圖1 中可以看出，2 個(gè)具有很高興趣相似度的研究人員在現(xiàn)實(shí)中有可能并不認(rèn)識(shí).但是，如果一組具有很高研究興趣相似度的研究人員同時(shí)在物理圖中具有連通性，那么這組研究人員就能通過彼此間的物理關(guān)系互相認(rèn)識(shí)，因此可以作為一組非常合適的研究人員參加研討會(huì).

Fig.1 Dual networks of researchers圖1 研究者雙網(wǎng)絡(luò)

為了發(fā)現(xiàn)雙網(wǎng)絡(luò)在概念圖中凝聚而物理圖中連通的子圖，能夠在線性或亞線性時(shí)間內(nèi)求解的k連通核（k-CCO）[18]和k連通truss（k-CT）[19]子圖模型相繼被提出.但上述模型存在的問題是，僅將概念圖構(gòu)建為邊上沒有權(quán)重的無向圖，而沒有考慮凝聚子圖的重要性，即影響力.Wu 等人[17]提出的概念圖中最密集而物理圖中連通DCS（dense connected subgraph）子圖模型，雖然考慮到概念圖中的邊權(quán)重，但根據(jù)最密集子圖定義，采用邊權(quán)重的平均值，并不能有效度量子圖的影響力，因?yàn)槠洳荒苡行x群點(diǎn)的影響.例如，一條邊的權(quán)重過低，它所在子圖的密集程度依然可能很大.

針對(duì)現(xiàn)有模型存在的問題，本文提出一種雙網(wǎng)絡(luò)中影響力k-連通truss（k-influential connected truss，k-ICT）子圖模型.給定雙網(wǎng)絡(luò)G(V,Ep,Ec,Ic)和正整數(shù)k，其中Ep為物理圖中的邊集，Ec為 概念圖中的邊集，Ic為Ec對(duì)應(yīng)的邊影響力集合.k-ICT 子圖為雙網(wǎng)絡(luò)中的誘導(dǎo)子圖H，當(dāng)且僅當(dāng)滿足3 個(gè)條件：1）在概念圖Gc中，H內(nèi)每條邊至少被k-2個(gè)三角形包含；2）在概念圖Gc中，H內(nèi)任意2 條邊都是三角形連通的，即2條邊在同一三角形內(nèi)或者所在三角形由一系列的三角形連接，其中每2 個(gè)相鄰三角形都共享一條邊；3）在物理圖Gp中，H是連通子圖.同時(shí)，k-ICT 子圖H的影響力為，即H的影響力為H中最小邊影響力值.這樣定義的優(yōu)勢(shì)在于最小影響力能夠保證H中每條 邊的影響力都不小于f(H).如果f(H)值很大，那么子圖內(nèi)每條邊的影響力都更大，因此該定義對(duì)離群點(diǎn)魯棒.而且k-ICT 子圖帶有影響力，當(dāng)發(fā)現(xiàn)影響力較大的子圖時(shí),相較k-CT 子圖，k-ICT 子圖規(guī)模更小，可解釋性則更強(qiáng).

根據(jù)k-ICT 子圖模型，本文重點(diǎn)研究雙網(wǎng)絡(luò)中top-r具有最大影響力k-ICT 子圖發(fā)現(xiàn)問題.為了解決該問題，需要確定與之相關(guān)的單網(wǎng)絡(luò)中最大影響力子圖發(fā)現(xiàn)算法是否能夠直接用于解決雙網(wǎng)絡(luò)中的最大影響力k-ICT 子圖發(fā)現(xiàn)問題.最近，文獻(xiàn)[12]分別提出了3 種基于在線全局搜索、局部搜索和離線索引的單網(wǎng)絡(luò)中最大影響力子圖發(fā)現(xiàn)算法.這3 種算法共同的核心思想是利用結(jié)點(diǎn)影響力不變性，迭代刪除當(dāng)前影響力最小的結(jié)點(diǎn)，從而使剩余子圖的影響力不斷提高，直到發(fā)現(xiàn)top-r個(gè)影響力最大的子圖.與本文問題不同的是，上述問題中使用結(jié)點(diǎn)的影響力來定義子圖的影響力，子圖影響力為子圖內(nèi)結(jié)點(diǎn)影響力的最小值，而本文工作是使用邊影響力來定義子圖影響力，如此定義能夠更好地反映子圖內(nèi)部結(jié)點(diǎn)之間關(guān)系的緊密相似性.隨后，Zheng 等人[20]提出一種通過不斷刪除影響力最小邊來發(fā)現(xiàn)單網(wǎng)絡(luò)中topr個(gè)影響力最大并三角形連通的k-truss 子圖（k-truss社區(qū)）算法，時(shí)間復(fù)雜度為O(m1.5)，m表示網(wǎng)絡(luò)中邊的數(shù)量.但是，通過圖2 實(shí)例可知，此算法并不可行.

Fig.2 Example of top-2 influential 3-truss community discovery in single network圖2 單網(wǎng)絡(luò)top-2 影響力3-truss 社區(qū)發(fā)現(xiàn)實(shí)例

如圖2 所示，文獻(xiàn)[20]所述的算法根據(jù)圖2（a）中的單網(wǎng)絡(luò)發(fā)現(xiàn)的top-2 影響力3-truss 社區(qū)為{(v1,v2)(v1,v4)(v2,v4)} 和{(v1,v2)(v1,v4)(v2,v4)(v3,v4)(v1,v3)}，影響力分別為7 和6.但通過觀察發(fā)現(xiàn)，由于帶影響力ktruss 社區(qū)為誘導(dǎo)子圖，根據(jù)誘導(dǎo)子圖定義只要結(jié)點(diǎn)存在并且結(jié)點(diǎn)之間在原圖中存在邊，那么該邊也在誘導(dǎo)子圖中.刪除邊 (v2,v3)后，由于剩余圖依然是3-truss 社區(qū)，所以結(jié)點(diǎn)v2和v3依然在子圖中并不會(huì)導(dǎo)致誘導(dǎo)子圖 {v1,v2,v3,v4}影 響力的變化.只有在結(jié)點(diǎn)v2或v3被刪除時(shí)子圖影響力才會(huì)變化.因此，由邊集合{(v1,v2)(v1,v4)(v2,v4)(v3,v4)(v1,v3)}得到的誘導(dǎo)子圖真實(shí)影響力為5.事實(shí)上，由結(jié)點(diǎn)集合 {v1,v2,v4} 和{v1,v3,v4}得到的誘導(dǎo)子圖才是真正的結(jié)果，影響力分別為7 和6.通過后文證明可知單網(wǎng)絡(luò)中影響力最大ktruss 社區(qū)發(fā)現(xiàn)問題為NP-難，因此雙網(wǎng)絡(luò)中影響力最大k-ICT 子圖發(fā)現(xiàn)問題依然為NP-難，多項(xiàng)式時(shí)間復(fù)雜度內(nèi)不存在精確解.

為解決雙網(wǎng)絡(luò)中top-r具有最大影響力k-ICT 子圖發(fā)現(xiàn)問題，本文首先不考慮概念圖中影響力，提出CT 分解算法計(jì)算每條邊的CT 數(shù)并對(duì)概念圖中的邊進(jìn)行CT 等價(jià)類劃分，然后根據(jù)劃分的等價(jià)類構(gòu)建CT 概要圖索引.利用該索引能夠快速還原對(duì)于不同給定k值的k-CT 子圖作為后續(xù)k-ICT 子圖發(fā)現(xiàn)的候選子圖，這樣能夠大量過濾掉不滿足結(jié)構(gòu)條件的結(jié)點(diǎn)和邊.其次，本文分別提出2 種發(fā)現(xiàn)top-r最大影響力k-ICT 子圖精確算法：Exact-G kICT 和Exact-LkICT.其中Exact-G kICT 算法從全局k-CT 子圖入手，不斷枚舉刪除影響力最小的邊和與其連接的結(jié)點(diǎn)，直到發(fā)現(xiàn)結(jié)果子圖；而Exact-LkICT 算法則采用從影響力最高的邊開始進(jìn)行局部子圖擴(kuò)展，直到在局部子圖中發(fā)現(xiàn)top-r最大影響力的k-ICT 子圖.

本文的主要貢獻(xiàn)點(diǎn)有4 個(gè)方面：

1）基于雙網(wǎng)絡(luò)中k-CT 子圖，提出了一種帶影響力的k-ICT 子圖模型，該模型能夠保證k-CT 子圖在概念圖中結(jié)點(diǎn)之間具有高度的凝聚性和相似性，并證明影響力最大k-ICT 子圖發(fā)現(xiàn)問題為NP-難問題；

2）提出一種基于概念圖中邊CT 等價(jià)類劃分的概要圖CT 索引結(jié)構(gòu)，根據(jù)該索引能夠針對(duì)不同k值快速還原包含k-ICT 子圖的候選子圖；

3）提出基于全局枚舉刪除和局部子圖擴(kuò)展策略的精確子圖搜索算法Exact-G kICT 和Exact-LkICT，實(shí)現(xiàn)高效top-r影響力最大k-ICT 子圖發(fā)現(xiàn)；

4）使用多個(gè)真實(shí)和合成數(shù)據(jù)集進(jìn)行大量實(shí)驗(yàn)驗(yàn)證本文提出算法的高效性和有效性.

1 相關(guān)工作

本文相關(guān)工作主要包括單網(wǎng)絡(luò)凝聚子圖挖掘、單網(wǎng)絡(luò)影響力凝聚子圖挖掘以及雙網(wǎng)絡(luò)凝聚子圖挖掘3 個(gè)方面.

1.1 單網(wǎng)絡(luò)凝聚子圖挖掘

單網(wǎng)絡(luò)凝聚子圖挖掘主要是發(fā)現(xiàn)圖中k-團(tuán)（kclique）、k-核（k-core）和k-捆（k-truss）等凝聚子圖結(jié)構(gòu).團(tuán)定義對(duì)子圖具有最強(qiáng)的約束條件，要求子圖中任意2 個(gè)結(jié)點(diǎn)之間均有邊連接.發(fā)現(xiàn)極大團(tuán)是NP-完全問題，Xu 等人[11]提出的BK 改進(jìn)算法是當(dāng)前已知最高效的極大團(tuán)枚舉算法.Yuan 等人[21]根據(jù)團(tuán)的定義提出了一種基于索引的社區(qū)發(fā)現(xiàn)算法.但是由于團(tuán)的定義過于嚴(yán)格，研究者開始研究基于團(tuán)松弛的凝聚子圖挖掘.k-核結(jié)構(gòu)從結(jié)點(diǎn)度的角度對(duì)子圖進(jìn)行放松，要求子圖內(nèi)任意結(jié)點(diǎn)度數(shù)不小于k.文獻(xiàn)[22]最先提出一種與圖中邊數(shù)成線性時(shí)間復(fù)雜度的核分解算法.文獻(xiàn)[23-24]分別提出了基于內(nèi)外存轉(zhuǎn)換的核分解算法.文獻(xiàn)[25]提出了在分布式環(huán)境下的核分解算法.文獻(xiàn)[26]分別提出了在一臺(tái)個(gè)人PC 機(jī)上的優(yōu)化k-核分解算法.Zhang 等人[27]提出了一種基于結(jié)點(diǎn)序的k-核維護(hù)算法，該算法能夠更新最少數(shù)量的邊.隨著應(yīng)用場(chǎng)景更加復(fù)雜，F(xiàn)ang 等人[28]提出了屬性圖上的k-核算法用于發(fā)現(xiàn)子圖內(nèi)結(jié)點(diǎn)屬性具有相似性的k-核子圖.Wang 等人[29]提出了在地理-社交網(wǎng)絡(luò)中基于半徑約束的k-核算法用于發(fā)現(xiàn)同時(shí)滿足子圖結(jié)構(gòu)和空間約束的凝聚子圖.k-truss 從邊的角度對(duì)團(tuán)進(jìn)行放松，規(guī)定k-truss 中每條邊至少被k-2個(gè)三角形包含.Cohen[30]最先提出k-truss 定義并給出多項(xiàng)式時(shí)間復(fù)雜度算法.隨后Wang 等人[31]提出一種改進(jìn)的truss 分解算法，通過對(duì)邊進(jìn)行排序加速算法效率.文獻(xiàn)[32]提出了一種基于圖數(shù)據(jù)庫技術(shù)的內(nèi)外存轉(zhuǎn)換k-truss 子圖發(fā)現(xiàn)算法.k-truss 子圖結(jié)構(gòu)還被廣泛用于建模社區(qū)，文獻(xiàn)[33]提出基于最小直徑約束的ktruss 社區(qū).文獻(xiàn)[34-35]分別利用truss 分解構(gòu)建圖索引，用于發(fā)現(xiàn)k-truss 社區(qū).同時(shí)，truss 還被擴(kuò)展應(yīng)用于不確定圖和屬性圖的社區(qū)搜索中[36].k-邊連通子圖從邊連通性對(duì)團(tuán)進(jìn)行放松，要求每對(duì)結(jié)點(diǎn)之間至少有k條邊獨(dú)立路徑，即任意刪除k-1 條邊子圖仍然連通.文獻(xiàn)[37]提出了k-邊連通凝聚子圖發(fā)現(xiàn)和更加高效的優(yōu)化算法.k-點(diǎn)連通凝聚子圖從子圖結(jié)點(diǎn)間結(jié)點(diǎn)連通度進(jìn)行放松，要求每對(duì)結(jié)點(diǎn)之間至少有k條結(jié)點(diǎn)獨(dú)立路徑，即任意刪除k-1個(gè)結(jié)點(diǎn)子圖仍然連通.李源等人[19]提出了允許子圖間存在重疊的k-點(diǎn)連通分量定義，并提出自頂向下、自底向上和混合框架的高效子圖發(fā)現(xiàn)算法.Wen 等人[38]提出了k-點(diǎn)連通分量枚舉算法.

1.2 單網(wǎng)絡(luò)影響力凝聚子圖挖掘

單網(wǎng)絡(luò)影響力凝聚子圖發(fā)現(xiàn)也稱為具有影響力社區(qū)發(fā)現(xiàn)，目的是要找出網(wǎng)絡(luò)中影響力最大的凝聚子圖.Li 等人[12]將該問題定義為從結(jié)點(diǎn)帶影響力的網(wǎng)絡(luò)中發(fā)現(xiàn)影響力最大的k-核子圖，子圖影響力用子圖中最小的結(jié)點(diǎn)影響力度量.首先，提出一種在線算法，該算法通過不斷刪除當(dāng)前圖中影響力最小的結(jié)點(diǎn)并保持剩余圖的結(jié)點(diǎn)度數(shù)約束，不斷發(fā)現(xiàn)影響力越來越大的k-核子圖.同時(shí)對(duì)于不同的k值，又提出一種線性索引結(jié)構(gòu)來加速最大影響力k-核子圖的發(fā)現(xiàn).接下來，Chen 等人[39]對(duì)文獻(xiàn)[12]中在線算法進(jìn)行了優(yōu)化，在求top-r影響力最大k-核子圖時(shí)，只計(jì)算最后r次迭代中的連通分量.但是文獻(xiàn)[12,39]所述的2 種在線算法都利用了整個(gè)網(wǎng)絡(luò)的全局結(jié)構(gòu).為了更好地優(yōu)化算法，Bi 等人[40]提出了一種基于局部搜索思想的算法，該算法從影響力最大的結(jié)點(diǎn)開始向外逐漸擴(kuò)展，直到發(fā)現(xiàn)最小的包含top-r影響力最大k-核子圖的局部子圖，該算法的時(shí)間復(fù)雜度與局部子圖大小成線性關(guān)系，與全局圖的大小無關(guān).文獻(xiàn)[12,39,40]所述的算法都是用結(jié)點(diǎn)影響力定義子圖影響力，Wang 等人[41]在二部圖中提出了一種通過邊緣權(quán)重定義的（α,β）-核社區(qū)模型，并根據(jù)包含（α,β）-核的最大連通分量建立索引，提出時(shí)間復(fù)雜度為O（δ×m）的剝離算法與局部擴(kuò)展算法進(jìn)行高效地社區(qū)搜索.Zheng 等人[20]提出一種通過邊影響力定義子圖影響力的影響力最大k-truss 社區(qū)模型并給出了多項(xiàng)式時(shí)間復(fù)雜度的top-r影響力最大k-truss 社區(qū)發(fā)現(xiàn)算法.該算法的思路同樣為迭代刪除影響力最小邊并不斷發(fā)現(xiàn)影響力更大的k-truss 社區(qū)，但是該算法存在的問題是忽略了影響力最大k-truss 社區(qū)為誘導(dǎo)子圖.如果有誘導(dǎo)子圖約束，那么該問題為NP 難問題，詳見第3 節(jié)中證明.為此，文獻(xiàn)[20]提出算法并不能找到topr影響力最大k-truss 社區(qū)的精確解.

1.3 雙網(wǎng)絡(luò)凝聚子圖挖掘

最近雙網(wǎng)絡(luò)得到研究者的廣泛關(guān)注[17].雙網(wǎng)絡(luò)G(V,Ep,Ec)包含2 個(gè)具有相同結(jié)點(diǎn)集但是不同邊集的圖，其中一個(gè)圖表示結(jié)點(diǎn)間的物理交互關(guān)系，另一個(gè)圖表示結(jié)點(diǎn)間的概念交互關(guān)系.但是現(xiàn)存的雙網(wǎng)絡(luò)凝聚子圖挖掘方法均存在一些問題.首先，Cui 等人[42]提出了k-核連通子圖模型，并且提出了高效精確的子圖發(fā)現(xiàn)算法，但是僅基于k-核的結(jié)點(diǎn)度數(shù)約束過于松弛，所發(fā)現(xiàn)子圖可能并不稠密.之后，李源等人[19]提出一種雙網(wǎng)絡(luò)k-truss 連通子圖模型，利用ktruss 的三角形結(jié)構(gòu)建模概念圖中的稠密區(qū)域，因此更加緊致，并提出了3 種高效的子圖發(fā)現(xiàn)算法.然而在實(shí)際應(yīng)用中，雙網(wǎng)絡(luò)中的概念圖應(yīng)該被建模為權(quán)重圖，邊權(quán)重表示結(jié)點(diǎn)之間的影響力，因此Wu 等人[17]提出了雙網(wǎng)絡(luò)中的DCS 問題，即發(fā)現(xiàn)概念圖中密集、物理圖中連通的子圖，并提出2 種基于不同刪除結(jié)點(diǎn)策略的貪婪算法來發(fā)現(xiàn)近似結(jié)果.但是，DCS 子圖模型使用概念圖中子圖邊權(quán)重的平均值度量子圖的密集程度魯棒性不足，并不能有效地消除離群點(diǎn)的影響，因?yàn)榧词挂粭l邊的權(quán)重過低，它所在子圖的密集程度依然可能很大.

基于上述問題，本文提出一種雙網(wǎng)絡(luò)中影響力k-連通truss 子圖模型，該模型使用子圖內(nèi)邊影響力的最小值定義子圖影響力，因此對(duì)離群點(diǎn)魯棒.影響力最大k-連通truss 子圖能夠有效建模雙網(wǎng)絡(luò)中在概念圖內(nèi)影響力最大且稠密，在物理圖內(nèi)連通的子圖.

2 概念及問題定義

本節(jié)主要介紹雙網(wǎng)絡(luò)相關(guān)概念及符號(hào)表示，影響力k-連通truss 子圖定義，及最大影響力k-連通truss 子圖發(fā)現(xiàn)問題定義和問題復(fù)雜性分析.

2.1 基本概念

給定一個(gè)雙網(wǎng)絡(luò)G(V,Ep,Ec,Ic)，圖Gp(V,Ep)和Gc(V,Ec,Ic)分別表示表示物理圖和概念圖，其中物理圖為無向無影響力圖，概念圖為無向有影響力圖.V為物理圖與概念圖相同的結(jié)點(diǎn)集合，Ep為物理圖的邊集合，Ec為 概念圖的邊集合，Ic為 邊集Ec對(duì)應(yīng)的邊權(quán)重集合即邊影響力集合.

對(duì)于一個(gè)無向帶邊影響力圖G(V,E,W)，V表示結(jié)點(diǎn)集合，n=|V|表 示結(jié)點(diǎn)個(gè)數(shù)；E表示邊集合，ei,j表示結(jié)點(diǎn)vi和vj之 間存在邊，即ei,j=(vi,vj)∈E，m=|E|表示邊的個(gè)數(shù)，W表示邊集合E對(duì)應(yīng)的影響力.使用m+n表示圖的規(guī)模.給定一個(gè)圖G中的結(jié)點(diǎn)u，使用NG(u)表示G中結(jié)點(diǎn)u的 鄰居集合，用degG(u)表 示G中結(jié)點(diǎn)u的度數(shù)，并且degG(u)=|NG(u)|.

給定一個(gè)結(jié)點(diǎn)集合H，G[H]={H,E(H)}表示結(jié)點(diǎn)集合H關(guān)于圖G的誘導(dǎo)子圖，如果滿足條件：H?V并且E(H)={(u,v)|?u,v∈H∧(u,v)∈E}.下面給出子圖影響力的定義.

定義 1.子圖影響力.給定一個(gè)無向帶邊影響力圖G(V,E,W) 和結(jié)點(diǎn)集合H(H?V)，那么誘導(dǎo)子圖G[H]的影響力為邊集E(H)中邊影響力的最小值，表示為

定義1 中選擇影響力最小值而不是選擇影響力平均值作為子圖影響力，是因?yàn)槠骄涤幸粋€(gè)缺點(diǎn)，即它對(duì)離群點(diǎn)不夠魯棒.具體地說，一個(gè)子圖即使f(G[H])很大，但是依然可能包括低影響力結(jié)點(diǎn)即離群點(diǎn)[17]，這些離群點(diǎn)并不是我們想要的結(jié)果.使用邊影響力最小值作為子圖影響力的好處是如果f(G[H])值很大，可以保證誘導(dǎo)子圖內(nèi)的每一條邊的影響力都很大，使得權(quán)值小的邊不可能出現(xiàn)在影響力大的子圖內(nèi).因此與平均值相比使用最小值定義子圖影響力能夠?qū)τ绊懥π〉倪呉簿褪请x群點(diǎn)更加魯棒.

三角形是構(gòu)成網(wǎng)絡(luò)最基本的高階結(jié)構(gòu)[31].三角形為一個(gè)長度為3 的環(huán)結(jié)構(gòu).給定環(huán)中的3 個(gè)結(jié)點(diǎn)u,v,w，那么三角形可以表示為 ?.根據(jù)三角形的定義，給出邊的三角形支持度的定義.給定圖G中的一條邊e=(u,v)∈EG，其支持度用sup(e,G)表 示，sup(e,G)=|{?|w∈V}|.換句話說，邊e的 支持度為圖G中包含e的三角形的個(gè)數(shù).當(dāng)沒有歧義時(shí)，sup(e,G)可以記為sup(e).如果e出 現(xiàn)在三角形 ?中，則e∈?.下面給出ktruss 子圖定義.

定義 2.k-truss 子圖[30]..給定無向帶邊影響力圖G和G的子圖G′，G′為一個(gè)k-truss 子圖，當(dāng)且僅當(dāng)每條邊e∈E(G′)被至少k-2個(gè)三角形包含，即?e∈E(G′),sup(e,G′)≥k-2，其中k≥2.極大k-truss 子圖用Tk表示.

根據(jù)定義2，一條邊可能屬于不同k值的k-truss子圖，那么對(duì)于一條邊e的truss 數(shù)可以定義為包含該邊使k最大的k-truss 子圖的k值，即φ (e)=max{k|E(Tk)}.

由于k-truss 子圖[31]可能不連通，下面給出三角形鄰接和三角形連通的定義來保證子圖的稠密性.

定義 3.三角形鄰接[19].給定圖G中的2 個(gè)三角形?1和 ?2，如果 ?1和 ?2有一條共同的邊，則稱 這2 個(gè) 三角形鄰接，表示為 ?1∩?2≠?.

定義 4.三角形連通[19].給定圖G中的2 條邊e1和e2，如果e1和e2在同一個(gè)三角形 ?中或者存在一系列圖G中的三角形 ?1,?2,…,?n，其中n≥2，使得e1∈?1，e2∈?n并且對(duì)于 1 ≤i

定義 5.k-truss 社區(qū)[34].給定一個(gè)圖G和正整數(shù)k（k≥2），一個(gè)子圖G′?G叫作k-truss 社區(qū)，滿足條件：1）G′為 一個(gè)k-truss 子圖；2）?e,e′∈E(G′)，e?e′.

在子圖影響力、k-truss 子圖和三角形連通定義的基礎(chǔ)上，雙網(wǎng)絡(luò)中k-ICT 子圖正式定義如下.

定義 6.k-ICT 子 圖.給定雙網(wǎng)絡(luò)G(V,Ep,Ec,Ic)正整數(shù)k（k≥3）和結(jié)點(diǎn)集合H（H?V），那么稱誘導(dǎo)子圖G[H]為k-ICT 子圖，滿足條件：

1）連通性.Gp[H]在 物理圖中連通；Gc[H]中的任意2 條邊都是三角形連通的.

2）稠密性.?e∈Ec(H)，sup(e,Gc[H])≥k-2，即Gc[H]為k-truss 子圖.

3）正值性.f(Gc[H])>0.

4）極大性.G[H]為滿足條件1）2）3）的極大誘導(dǎo)子圖，即不存在滿足條件1）2）3）的G[H′]∈G使得H?H′并且f(Gc[H])≤f(Gc[H′]).

另外給定一個(gè)雙網(wǎng)絡(luò)G(V,Ep,Ec,Ic)，其最大ICT數(shù)記為kmax(G)，表示使得k-ICT 子圖不為空的最大k值.

圖3 給出了雙網(wǎng)絡(luò)的示意圖，其中由結(jié)點(diǎn)集合{v1,v2,v3,v4}得到的誘導(dǎo)子圖為3-ICT 子圖，影響力為2；由 {v4,v5,v6,v7}得到的誘導(dǎo)子圖為4-ICT 子圖.這2個(gè)子圖全都滿足k-ICT 子圖定義中的約束條件.但是，由{v1,v3,v4}得到的誘導(dǎo)子圖就不是3-ICT，因?yàn)樵撟訄D不滿足子圖極大條件約束，存在f({v1,v3,v4})=f({v1,v2,v3,v4})=2.

Fig.3 Dual networks圖3 雙網(wǎng)絡(luò)

2.2 問題定義

問題1.給定雙網(wǎng)絡(luò)G(V,Ep,Ec,Ic)和正整數(shù)k（k≥3），從G中發(fā)現(xiàn)top-r影響力最大k-ICT 子圖.

下面分析問題1 的復(fù)雜性.首先將問題1 簡化為單網(wǎng)絡(luò)中top-1 影響力最大且滿足三角形連通的極大k-truss 子圖發(fā)現(xiàn)問題，即問題2.然后，如果能夠證明問題2 是NP-難問題，那么由于問題1 還需要同時(shí)考慮子圖在物理圖中的連通性更加復(fù)雜，因此問題1 同樣為NP-難問題.

問題 2.給定無向帶邊影響力圖G(V,E,W)和正整數(shù)k（k≥3），從圖G中發(fā)現(xiàn)影響力最大且滿足三角形連通約束的極大k-truss 子圖.

定理 1.問題2 為NP-難問題.

證明.為了證明問題2 是NP-難的，本文將問題2 歸約為另一個(gè)著名NP-難的極大團(tuán)問題.這里考慮極大團(tuán)問題的判定性版本，圖G中是否存在一個(gè)結(jié)點(diǎn)個(gè)數(shù)為k的團(tuán).首先對(duì)問題2 中的圖G進(jìn)行構(gòu)造，對(duì)于圖G，任意邊e∈E，w(e)=1；對(duì)于任意結(jié)點(diǎn)u和v，如果u和v在G中不存在邊，則添加邊 (u,v)并使得w((u,v))=-1.同時(shí)，根據(jù)圖G構(gòu)建無影響力圖G′，使得E′=E.對(duì)于圖G中滿足問題2 中條件的解需要的影響力最大，根據(jù)子圖影響力定義，該結(jié)果子圖中不能有負(fù)邊，因此結(jié)果子圖內(nèi)部任意結(jié)點(diǎn)間邊的影響力必須為1，也就是說該結(jié)果子圖是由影響力為1 的邊構(gòu)成的團(tuán).如果在圖G中存在規(guī)模大于k的影響力最大且滿足三角形連通約束的極大k-truss 子圖，那么在圖G′中就存在一個(gè)規(guī)模大于k的團(tuán).反過來，如果在圖G′中 就存在一個(gè)規(guī)模大于k的團(tuán)，那么在圖G中也存在一個(gè)規(guī)模大于k且任意結(jié)點(diǎn)之間邊影響力都為1 的影響力最大且滿足三角形連通約束的極大k-truss 子圖.因此，問題2 為NP-難的.證畢.根據(jù)定理1，由于問題2 是NP-難的，那么本文要解決的問題1 同樣是NP-難問題.在接下來的第3 和第4 節(jié)中將詳細(xì)介紹top-r影響力最大k-ICT 子圖發(fā)現(xiàn)問題解法.

3 雙網(wǎng)絡(luò)中CT 索引結(jié)構(gòu)

本節(jié)在構(gòu)建雙網(wǎng)絡(luò)中CT 索引時(shí)，調(diào)用了文獻(xiàn)[19]中的kCT-FIND 算法來發(fā)現(xiàn)k-CT 子圖.CT 索引為根據(jù)k-CT 子圖分解構(gòu)建的一種概要圖結(jié)構(gòu).根據(jù)該索引能夠更好地確定k-ICT 子圖在雙網(wǎng)絡(luò)中更小的范圍，從而加速子圖發(fā)現(xiàn)算法的搜索效率.接下來，首先研究CT 索引設(shè)計(jì)，然后給出CT 索引構(gòu)建算法及時(shí)間復(fù)雜度分析.

3.1 CT 等價(jià)類劃分

為了能夠更高效地發(fā)現(xiàn)top-r影響力最大的k-ICT 子圖，一個(gè)關(guān)鍵的問題是先要確定k-ICT 子圖可能在雙網(wǎng)絡(luò)G中出現(xiàn)的位置，如果能夠預(yù)先對(duì)雙網(wǎng)絡(luò)進(jìn)行范圍收縮，并且保證收縮后的子圖內(nèi)一定包含k-ICT 子圖，那么就能夠在更小的子圖范圍內(nèi)發(fā)現(xiàn)結(jié)果，從而提高算法效率.而且參數(shù)k的變化對(duì)子圖發(fā)現(xiàn)也有很大影響，為了能夠滿足對(duì)于不同k值的k-ICT 子圖的快速發(fā)現(xiàn)，構(gòu)建隨k值變化的子圖層次結(jié)構(gòu)索引也非常必要.本節(jié)提出的CT 索引為根據(jù)k-CT 子圖等價(jià)類劃分構(gòu)建的一種概要圖結(jié)構(gòu).k-CT 子圖對(duì)k-ICT 子圖約束進(jìn)行了放松，不考慮概念圖中邊上的影響力，同時(shí)不要求是誘導(dǎo)子圖.定義7 給出k-CT 子圖定義.

定義 7.k-CT 子圖[19].給定雙網(wǎng)絡(luò)G(V,Ep,Ec)和正整數(shù)k（k≥3），那么子圖G′為k-CT 子圖當(dāng)且僅當(dāng)：

1）G′在概念圖中為k-truss 社區(qū)；

2）G′在物理圖中連通；

3）G′為滿足條件1）和條件2）的極大子圖.

定理 2.給定k-ICT 子圖g，子圖g一定被某個(gè)k-CT 子圖g′所 包含，即g?g′.

證明.根據(jù)定義6 和定義7，k-ICT 子圖除了具備k-CT 子圖約束之外，還要求其為誘導(dǎo)子圖，也就是說k-ICT 子圖在概念圖中的任意邊支持度都大于等于k-2，相比于k-CT 子圖要求更加嚴(yán)格，k-CT 子圖包含結(jié)點(diǎn)構(gòu)成的誘導(dǎo)子圖可能包含支持度小于k-2的邊.同時(shí)，k-ICT 子圖概念圖中邊還包含影響力.因此，能夠確定如果存在k-ICT 子圖g，其一定被某個(gè)k-CT子圖g′包含.證畢.

根據(jù)定義7，一旦得到了所有的k-CT 子圖集合，就能從中發(fā)現(xiàn)包含的top-r影響力最大k-ICT 子圖.因此，CT 索引設(shè)計(jì)的思想就是通過對(duì)CT 子圖中的邊進(jìn)行等價(jià)類劃分，從而能夠有效存儲(chǔ)不同k值的k-CT 子圖.具體做法為：1）對(duì)雙網(wǎng)絡(luò)進(jìn)行k-CT 子圖分解，求得雙網(wǎng)絡(luò)概念圖中每條邊的CT 數(shù)；2）根據(jù)概念圖每條邊的CT 數(shù)和邊與邊之間在概念圖的三角形連通性，對(duì)概念圖中的邊進(jìn)行等價(jià)類劃分.

算法 1.CT 分解（CT_Decomposition）.

算法1 給出了CT 分解算法用來計(jì)算每條邊的CT 數(shù).該算法的核心思想是從雙網(wǎng)絡(luò)中的概念圖中不斷刪除當(dāng)前支持度最小的邊，當(dāng)一條邊被刪除時(shí)，其所在的k-CT 子圖的k值就是該邊的CT 數(shù).另外在刪除邊的同時(shí)，需要保持每個(gè)子圖中結(jié)點(diǎn)在物理圖中的連通性，如果物理圖變得不連通，則需要將物理圖中每個(gè)連通分量中的結(jié)點(diǎn)對(duì)應(yīng)到概念圖中，并重新計(jì)算每個(gè)子圖中邊的支持度.如此循環(huán)直到剩余邊都滿足條件為止.

具體來講，首先設(shè)置k=2，先找出不在任何k-CT（k≥3）中的邊（行①）.然后，當(dāng)Ec≠?，先找出物理圖中的連通分支，概念圖中跨不同連通分支的邊都被刪除，同時(shí)每個(gè)連通分支內(nèi)部在概念圖中不滿足支持度要求的邊都被刪除（行②～?）.概念圖中的孤立點(diǎn)也被刪除（行?）.對(duì)于剩余概念圖中的三角形連通分量，如果其在物理圖中不連通，還需將其分解為不同子圖，放入隊(duì)列中進(jìn)行后續(xù)處理（行?～?）.當(dāng)發(fā)現(xiàn)所有的（k-1）-CT 子圖中的邊都被刪除，而Ec不為空，則k增加1（行?）.最后，當(dāng)Ec中所有邊都被刪除時(shí)，說明每條邊的CT 數(shù)都已經(jīng)計(jì)算完成并返回結(jié)果（行?）.

接下來分析算法1 的時(shí)間復(fù)雜度，計(jì)算概念圖中邊的支持度和三角形連通性的時(shí)間為O(|Ec|1.5)，檢查物理圖中連通性的時(shí)間為O(|Ep|).在一次隊(duì)列的循環(huán)中，連通分量分裂的平均深度為h，最大非空k-CT的k值為km′ax，那么整個(gè)算法時(shí)間復(fù)雜度為O(km′ax×|Ec|1.5×h).圖4 給出了圖3(b)中每條邊的CT 數(shù)，如方框內(nèi)數(shù)字所示.

Fig.4 Number of CT on each edge in fig.3(b)圖4 圖3(b)內(nèi)每條邊的CT 數(shù)

定義 10.k-三角形.給定一個(gè)三角形 ?uvw?Gc,如果三角形中每條邊的CT 數(shù)都不小于k，即min{τ(u,v),τ(u,w),τ(v,w)}≥k,則 ?uvw為一個(gè)k-三角形.

3.2 CT 索引設(shè)計(jì)與構(gòu)建

根據(jù)定義12，雙網(wǎng)絡(luò)概念圖中的邊被劃分為一系列互相之間交集為空的等價(jià)類，其中每個(gè)等價(jià)類為包含等價(jià)邊的集合，該邊集合為某個(gè)k-CT 子圖或子圖的組成部分.本節(jié)基于k-CT 等價(jià)類設(shè)計(jì)CT 索引.CT 索引可以表示為一個(gè)概要圖 G(V,E)，其中V為超結(jié)點(diǎn)集合，E為超邊集合 E ?V×V.超節(jié)點(diǎn)∈V表示一個(gè)等價(jià)類，超邊 (,)∈E表示2 個(gè)等價(jià)類中的邊是三角形連通的，即存在e∈和e′∈使得e?e′.

CT 索引有2 個(gè)優(yōu)點(diǎn)：

1）CT 索引能夠保存雙網(wǎng)絡(luò)中所有k-CT 子圖(k≥3)結(jié)構(gòu).原因是根據(jù)CT 算法分解能夠得到每條邊的CT 數(shù)，實(shí)際上該過程就是求解雙網(wǎng)絡(luò)中對(duì)于所有k值的k-CT 子圖過程，然后根據(jù)邊的CT 數(shù)和邊之間的三角形連通關(guān)系就能還原相應(yīng)的k-CT 子圖.在概要圖 G中的超節(jié)點(diǎn)為等價(jià)類邊集合，超邊為邊集之間的三角形連通關(guān)系，提供還原k-CT 子圖的全部信息，因此能夠保存所有k-CT 子圖.而且值得注意的是，單個(gè)等價(jià)類邊集內(nèi)結(jié)點(diǎn)集合在物理圖中不要求必須連通，只要根據(jù)CT 索引還原的k-CT 子圖中結(jié)點(diǎn)在物理圖中連通即可.

2）由于CT 索引概要圖中的超節(jié)點(diǎn)為雙網(wǎng)絡(luò)概念圖中邊的劃分，因此每條邊只出現(xiàn)在1 個(gè)超節(jié)點(diǎn)中，沒有任何存儲(chǔ)空間的冗余，占用的空間復(fù)雜度為O(|Ec|).

根據(jù)CT 索引中概要圖 G還原所有k-CT 子圖的方法為：首先規(guī)定每個(gè)等價(jià)類對(duì)應(yīng)超節(jié)點(diǎn)的值為等價(jià)類中邊的CT 數(shù)記為；然后從圖中找出所有≥k的超節(jié)點(diǎn)集合 V′；最終 V′在概要圖 G中的誘導(dǎo)子圖中不同的連通分支就對(duì)應(yīng)所有的k-CT 子圖.

圖5 展示了圖3 中雙網(wǎng)絡(luò)的CT 索引，該索引的概要圖中包含2 個(gè)超節(jié)點(diǎn)和，其中k1=3，k2=4.和之間存在一條超邊表示和內(nèi)的邊三角形連通.從圖5 可知，雙網(wǎng)絡(luò)中存在一個(gè)3-CT 子圖和一個(gè)4-CT 子圖，3-CT 為超節(jié)點(diǎn)集合 {,}對(duì)應(yīng)的邊集，其在概念圖中共包含13 條邊；4-CT 為超節(jié)點(diǎn)對(duì)應(yīng)的邊集，其在概念圖中共包含6 條邊.

Fig.5 CT index of dual-networks in fig.3圖5 圖3 中雙網(wǎng)絡(luò)CT 索引

算法 2.CT 索引構(gòu)建（CT_Index_Construction）.

接下來研究如何構(gòu)建CT 索引.算法2 給出了CT 索引的構(gòu)建過程.算法2 的主要思想是：首先根據(jù)每條邊的CT 數(shù)，從 CT 數(shù)小的邊開始通過廣度優(yōu)先搜索找到該條邊e所在 τ(e)-CT 等價(jià)類中的所有邊作為一個(gè)CT 索引概要圖中的超節(jié)點(diǎn)；然后根據(jù)不同超節(jié)點(diǎn)內(nèi)部邊之間的三角形連通性構(gòu)建超邊；最終構(gòu)建成為CT 索引概要圖 G(V,E).

CT 索引構(gòu)建算法詳細(xì)偽代碼如算法2 所示.算法開始是初始化階段，首先利用CT 分解算法計(jì)算概念圖中每條邊的CT 數(shù)，然后根據(jù)每條邊的CT 數(shù)將邊e放置到不同的集合 Φk中.對(duì)于每條邊e∈Ec，維護(hù)2 個(gè)不同數(shù)據(jù)結(jié)構(gòu)的變量，其中p為布爾型變量，其表示邊e在初始化過程中是否已經(jīng)被使用過，并且初始化為 false；L表示一個(gè)超節(jié)點(diǎn)集合，該集合中每個(gè)超節(jié)點(diǎn)之前已經(jīng)被處理過，其中 τ()

接下來是索引概要圖的構(gòu)建階段，算法根據(jù)k值從小到大的順序依次訪問 Φk中所有的邊，將每條邊加入到唯一的超節(jié)點(diǎn)中，并且建立超節(jié)點(diǎn)之間的超邊.首先，對(duì)于 Φk中的邊e，為其創(chuàng)建一個(gè)與之所在k-CT 等價(jià)類Ce對(duì)應(yīng)的超節(jié)點(diǎn)；然后將邊e作為種子對(duì)Ec進(jìn)行寬度優(yōu)先遍歷，將與e為k-三角形連通的邊加入到中.在遍歷時(shí)同時(shí)檢查是否存在超節(jié)點(diǎn)（τ()<τ()=k）通過e與三角形連通，如果存在，則構(gòu)建超邊（,）.同時(shí)在遍歷過程中，如果在k-三角形中存在邊e′使得 τ(e′)>k，那么當(dāng)前e所在的超節(jié)點(diǎn)與未來e′所在的超節(jié)點(diǎn)三角形連通，并將e加入到e′.L中，等待將來被處理（行⑨～?）.當(dāng)邊e被處理完成后將其從 Φk和Ec中刪除（行?），最后返回CT 索引概要圖 G(V,E)（行?）.函 數(shù)Edge_Processing用來處理與當(dāng)前訪問邊構(gòu)成k-三角形的其余2 條邊，當(dāng)邊CT數(shù)等于k，則將該邊加入當(dāng)前超節(jié)點(diǎn)，當(dāng)邊CT 數(shù)大于k，則將當(dāng)前超節(jié)點(diǎn)的編號(hào)記錄到邊的L隊(duì)列中（行?～?）.

算法2 中計(jì)算所有邊CT 數(shù)的CT 分解算法時(shí)間復(fù)雜度為，在索引構(gòu)建階段，概念圖中的每個(gè)三角形剛好被檢測(cè)一次，因此時(shí)間復(fù)雜度為概念圖中的三角形數(shù)量O(|Ec|1.5).最終算法2 的整體時(shí)間復(fù)雜度為.空間復(fù)雜度分析為O(|Ec|).

4 雙網(wǎng)絡(luò)中k-ICT 子圖發(fā)現(xiàn)算法

根據(jù)第3 節(jié)提出的雙網(wǎng)絡(luò)中CT 索引結(jié)構(gòu)，對(duì)于給定的k值，首先根據(jù)CT 索引結(jié)構(gòu)中的概要圖還原出所有的k-CT 子圖，這樣就不用每次從整個(gè)雙網(wǎng)絡(luò)中尋找top-r最大影響力k-ICT 子圖.根據(jù)定理2，k-ICT 子圖一定存在于某個(gè)k-CT 子圖中.因此，本節(jié)的任務(wù)就為從CT 索引獲得的k-CT 子圖中發(fā)現(xiàn)top-r影響力最大的k-ICT 子圖.

較k-CT 子圖，k-ICT 子圖主要有2 點(diǎn)不同：1）k-ICT 子圖概念圖中帶有邊影響力；2）k-ICT 子圖中概念圖為誘導(dǎo)子圖.針對(duì)第1 點(diǎn)不同，在一個(gè)k-CT子圖中可能包含若干個(gè)k-ICT 子圖，因?yàn)閗-ICT 子圖能夠滿足相同的結(jié)構(gòu)性約束，但是具有不同的子圖影響力，因此可以作為不同的k-ICT 子圖，也就是說k-ICT子圖的規(guī)模比滿足結(jié)構(gòu)極大條件的k-CT 子圖更小.針對(duì)第2 點(diǎn)不同，正是由于誘導(dǎo)子圖的約束，導(dǎo)致最大影響力k-ICT 子圖發(fā)現(xiàn)問題為NP-難的.對(duì)于誘導(dǎo)子圖，單純的刪除邊可能并不能改變子圖的影響力，只有當(dāng)子圖中的結(jié)點(diǎn)發(fā)生變化時(shí)，子圖的影響力才可能發(fā)生變化，正是由于該特性給k-ICT 子圖發(fā)現(xiàn)帶來巨大挑戰(zhàn).由于直接根據(jù)文獻(xiàn)[23]中的方法并不能求得top-r最大影響力k-ICT 子圖的精確解，于是本節(jié)分別基于全局枚舉刪除和局部子圖擴(kuò)展思想提出2 種top-r最大影響力k-ICT 子圖精確發(fā)現(xiàn)算法，稱為Exact-G kICT 和Exact-LkICT，并分析2 種算法的復(fù)雜度.

4.1 全局k -ICT 子圖發(fā)現(xiàn)算法Exact-GkICT

4.1.1 Exact-GkICT 算法思想

本節(jié)提出了基于全局枚舉刪除的k-ICT 子圖發(fā)現(xiàn)算法Exact-G kICT，其主要思想為從包含k-ICT 子圖的k-CT 誘導(dǎo)子圖中不斷刪除影響力最小的邊，如果刪除邊后誘導(dǎo)子圖的影響力沒變化，則刪除與影響力最小邊鄰接的結(jié)點(diǎn)，如此往復(fù)，直到邊集為空停止.在不斷的刪除邊或點(diǎn)的過程中能夠在k-CT 誘導(dǎo)子圖中發(fā)現(xiàn)一系列滿足結(jié)構(gòu)性約束的子圖，這些子圖就稱為k-ICT 子圖，而且越往后得到的子圖影響力越大，最后從得到的候選結(jié)果集中輸出前r個(gè)最大的子圖作為top-r最大影響力k-ICT 子圖.

算法 3.GExact-kICT 算法.

4.1.2 Exact-G kICT 算法描述

根據(jù)4.1.1 節(jié)的算法思想，本節(jié)提出了完整的Exact-G kICT 算法用于發(fā)現(xiàn)top-r最大影響力k-ICT 子圖，算法偽代碼如算法3 所示.整個(gè)算法可以分為3個(gè)主要步驟：第1 步，從CT 索引概要圖中獲得所有的k-CT 子圖，使用Gk-CT表示（行②）.G k-CT中包含每個(gè)k-CT 子圖對(duì)應(yīng)的物理圖和概念圖中的子圖.第2 步，通過調(diào)用函數(shù)FIND-INDUCED-KCT，找到所有k-CT子圖中包含的滿足k-CT 條件的誘導(dǎo)子圖，存放于集合 T 中（行③）.由于k-CT 子圖中結(jié)點(diǎn)集合在雙網(wǎng)絡(luò)中的誘導(dǎo)子圖可能包含CT 數(shù)小于k-2的邊，需要將這些邊及其鄰接的結(jié)點(diǎn)級(jí)聯(lián)刪除，直到發(fā)現(xiàn)所有滿足條件的k-CT 誘導(dǎo)子圖.第3 步，通過調(diào)用函數(shù)FIND-KICT，從當(dāng)前得到的k-CT 誘導(dǎo)子圖集合中找到所有候選的k-ICT 子圖（行④）.最終輸出前r個(gè)影響力最大k-ICT 子圖作為結(jié)果（行⑤）.

函數(shù)FIND-INDUCED-KCT用于發(fā)現(xiàn)k-CT 子圖中所有包含的k-CT 誘導(dǎo)子圖.首先如果對(duì)于當(dāng)前的k-CT 子圖中結(jié)點(diǎn)得到的誘導(dǎo)子圖中不包含任何CT 數(shù)小于k-2的邊，則可直接將該子圖放入 T中（行⑧～⑨）；否則，需要分別刪除不滿足條件邊對(duì)應(yīng)的2 個(gè)結(jié)點(diǎn)，然后再遞歸調(diào)用函數(shù)FIND-INDUCED-KCT，從刪除結(jié)點(diǎn)后的子圖中發(fā)現(xiàn)k-CT 誘導(dǎo)子圖，最終結(jié)果都存放于 T 中（行?～?）.整個(gè)循環(huán)過程直至Gk-CT中不存在CT 數(shù)小于2 的邊為止，得到的結(jié)果都是k-CT誘導(dǎo)子圖（行⑦～?）.

函數(shù)FIND-KICT用于發(fā)現(xiàn)k-CT 誘導(dǎo)子圖中包含的k-ICT 子圖.首先，當(dāng)前的所有k-CT 誘導(dǎo)子圖自身就為k-ICT 子圖，計(jì)算子圖影響力 T 并將 T 放入候選結(jié)果集 Rcand中（行?）.然后當(dāng) T不為空時(shí)，不斷從中刪除影響力最小的邊，并得到新的影響力更大的k-ICT子圖（行?～?）.在具體實(shí)現(xiàn)過程中可將所有子圖按照影響力從小到大順序存放在優(yōu)先隊(duì)列中，并通過最好優(yōu)先方式進(jìn)行處理.在刪除影響力最小的邊以及隨之不滿足條件的邊后，如果子圖中三角形連通分量數(shù)和結(jié)點(diǎn)沒有變化，則需要進(jìn)一步分別刪除影響力最小邊對(duì)應(yīng)的結(jié)點(diǎn)，并找到子圖中的k-ICT 子圖（行?～?）.否則，對(duì)當(dāng)前刪除邊后子圖的每個(gè)三角形連通分量進(jìn)行處理，找到其中的k-ICT 子圖（行?～?）.同時(shí)分別將獲得的k-ICT 子圖放入 T 和 Rcand中.

算法Exact-G kICT 的時(shí)間復(fù)雜度主要受k-CT 子圖Gk-CT的大小影響，因?yàn)榻Y(jié)果子圖為誘導(dǎo)子圖，只有當(dāng)子圖中結(jié)點(diǎn)發(fā)生變化，子圖影響力才可能變化.在刪除影響力最小邊時(shí)，需要枚舉刪除邊相鄰的2 個(gè)結(jié)點(diǎn).在最壞情況下需要枚舉刪除每條邊對(duì)應(yīng)的結(jié)點(diǎn)，因此最壞時(shí)間復(fù)雜度為O(2|Vk-CT|×|Ek-CT|1.5).但是在實(shí)際情況中由于邊或結(jié)點(diǎn)的刪除會(huì)引起其他邊和結(jié)點(diǎn)的級(jí)聯(lián)刪除，因此算法實(shí)際時(shí)間復(fù)雜度要遠(yuǎn)小于最壞時(shí)間復(fù)雜度.

接下來使用圖3 中的雙網(wǎng)絡(luò)來演示算法Exact-GkICT，假設(shè)要發(fā)現(xiàn)top-2 最大影響力3-ICT 子圖.首先整個(gè)雙網(wǎng)絡(luò)G就為一個(gè)3-CT 誘導(dǎo)子圖，同樣為一個(gè)3-ICT 子圖，影響力f(Gc)=1.接下來刪除影響力最小的邊 (v3,v5)，其刪除導(dǎo)致邊 (v2,v5)的刪除.這時(shí)整個(gè)圖劃分為2 個(gè)三角形連通分量{v1,v2,v3,v4}和{v4,v5,v6,v7}，同樣也是2 個(gè)3-ICT 子圖，影響力分別為2 和5.然后分別從這2 個(gè)3-ICT 子圖中刪除最小影響力的邊，值得注意的是，在刪除邊 (v5,v6)時(shí)，需要分別枚舉刪除結(jié)點(diǎn)v5和v6，這樣邊 (v5,v6)才能夠在誘導(dǎo)子圖中被真正刪除.最終得到的結(jié)果為由結(jié)點(diǎn)集合{v1,v2,v3}和{v4,v5,v7}誘導(dǎo)構(gòu)成的3-ICT 子圖，對(duì)應(yīng)影響力分別為10 和7.

4.2 局部k -ICT 子圖發(fā)現(xiàn)算法Exact-LkICT

4.2.1 Exact-LkICT 算法思想

在4.1 節(jié)中提出的全局枚舉刪除算法Exact-GkICT 中可以看出，影響力最大的子圖往往在算法最后才能計(jì)算出來.原因是全局算法首先刪除影響力最小的邊，產(chǎn)生的子圖影響力是升序排列.但是，當(dāng)想要發(fā)現(xiàn)top-r最大影響力k-ICT 子圖中的r值較小時(shí)，算法Exact-G kICT 仍然需要枚舉刪除整個(gè)k-CT 子圖中的結(jié)點(diǎn)，導(dǎo)致算法效率較低.例如，為了發(fā)現(xiàn)top-1最大影響力k-ICT 子圖，需要首先發(fā)現(xiàn)top-n，top-（n-1），…，top-2 影響力最大的子圖.

為了能夠更快地發(fā)現(xiàn)較小r值的top-r最大影響力k-ICT 子圖，本節(jié)提出了一種基于局部子圖擴(kuò)展的算法Exact-LkICT.該算法的主要思想是從包含k-ICT子圖的k-CT 子圖對(duì)應(yīng)概念圖中影響力最大的邊入手，將邊影響力按照從大到小進(jìn)行排序.然后，確定能夠包含top-r最大影響力k-ICT 子圖最小邊集合的規(guī)模，也就是初始局部子圖的大小.這樣就可以根據(jù)邊的影響力由大到小從k-CT 子圖不斷向局部子圖中加入邊，如果當(dāng)前的局部子圖中包含k-ICT 子圖的數(shù)量小于r，則相應(yīng)擴(kuò)大局部子圖規(guī)模，直到該局部子圖中包含top-r最大影響力k-ICT 子圖為止.

為了保證算法Exact-LkICT 的順利執(zhí)行，一個(gè)很重要的問題就是確定初始局部子圖的規(guī)模，需要估計(jì)可能包含top-r最大影響力k-ICT 子圖的局部子圖內(nèi)邊集合的大小，也就是該局部子圖內(nèi)至少存在相同的邊數(shù)量才可能包含結(jié)果子圖集合.定理3 給出證明.

算法 4.Exact-LkICT.

4.2.2 Exact-LkICT 算法描述

根據(jù)4.2.1 節(jié)中給出的算法思想，本節(jié)提出局部擴(kuò)展的Exact-LkICT 算法，偽代碼如算法4 所示.首先，對(duì)變量進(jìn)行初始化，其中 δ表示局部子圖規(guī)模擴(kuò)展的倍數(shù)（行①）.其次，根據(jù)CT 索引中的概要圖獲得k-CT 子圖Gk-CT.因?yàn)樾枰獙k-CT的概念圖中邊按照影響力由大到小向局部子圖中添加，因此對(duì)Ec(Gk-CT) 中的邊按照影響力進(jìn)行降序排序（行③）.然后，給定G1為初始局部子圖，該子圖中包含Ec(Gk-CT) 中前k×(k-1)/2+(r-1)×k條影響力最大的邊（行④）.接下來，當(dāng)|Ec(Gi)|≤|Ec(Gk-CT) |且r′>0時(shí)，說明從當(dāng)前局部子圖中發(fā)現(xiàn)的結(jié)果還不夠r個(gè)，需要對(duì)當(dāng)前子圖繼續(xù)進(jìn)行擴(kuò)展，從Ec(Gk-CT) 中接續(xù)向當(dāng)前子圖中增量加入影響力大的邊，直到局部子圖規(guī)模大于Gk-CT或者結(jié)果子圖數(shù)量達(dá)到r為止（行⑤～?）.

下面分別介紹函數(shù)FIND-INDUCED-KCT-R（行⑥）和函數(shù)FIND-KICT-R（行⑦）.函數(shù)FIND-INDUCEDKCT-R與算法3 中函數(shù)FIND-INDUCED-KCT功能類似，從當(dāng)前局部雙網(wǎng)絡(luò)Gi中發(fā)現(xiàn)k-CT 誘導(dǎo)子圖.假定Gi中影響力最小邊對(duì)應(yīng)的影響力為wi，區(qū)別在于函數(shù)FIND-INDUCED-KCT-R需要從Gi概念圖對(duì)應(yīng)的誘導(dǎo)子圖中額外刪除影響力小于wi的邊.同時(shí)如果在刪除邊或結(jié)點(diǎn)的過程中發(fā)現(xiàn)已經(jīng)開始刪除Gi-1中的邊或點(diǎn)則停止，因?yàn)榇藭r(shí)子圖中已經(jīng)不可能包含新的誘導(dǎo)子圖，目的是不重復(fù)發(fā)現(xiàn)之前循環(huán)中已經(jīng)發(fā)現(xiàn)的誘導(dǎo)子圖.對(duì)于函數(shù)FIND-KICT-R，同樣只需發(fā)現(xiàn)當(dāng)前Gi中新包含的k-ICT 子圖，而不是重復(fù)發(fā)現(xiàn)之前Gt（t

算法Exact-LkICT 采用增量計(jì)算方式不斷對(duì)當(dāng)前局部子圖進(jìn)行擴(kuò)展，保證每個(gè)top-r最大影響力k-ICT 子圖都能被發(fā)現(xiàn)且僅被發(fā)現(xiàn)一次.該算法的時(shí)間復(fù)雜度與最后發(fā)現(xiàn)的包含top-r結(jié)果的局部雙網(wǎng)絡(luò)Gi中結(jié)點(diǎn)數(shù)量有關(guān)，最壞情況下時(shí)間復(fù)雜度為O(2|Vi|×|Ei|1.5).由此可以看出，算法Exact-LkICT 的時(shí)間復(fù)雜度僅與包含結(jié)果的雙網(wǎng)絡(luò)子圖大小有關(guān)而與整個(gè)Gk-CT規(guī)模無關(guān)，且當(dāng)r值越小時(shí)，算法Exact-LkICT 效率更高.

下面使用圖3 中的雙網(wǎng)絡(luò)來演示算法Exact-LkICT，假設(shè)要發(fā)現(xiàn)top-1 最大影響力3-ICT 子圖.首先，根據(jù)CT 索引獲得3-CT 子圖，其概念子圖中的邊為整個(gè)概念圖中的邊；然后按照影響力對(duì)概念圖中的邊由大到小進(jìn)行排序，并將影響力最大的3 條邊即 (v4,v7)，(v3,v4) 和 (v1,v3) 加入到G1中（w1=12），并得到結(jié)點(diǎn)集合 {v1,v3,v4,v7}在雙網(wǎng)絡(luò)中的誘導(dǎo)子圖.由于該誘導(dǎo)子圖包含邊 (v1,v4)，w((v1,v4))=2

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)環(huán)境配置

本文使用真實(shí)數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試，評(píng)估的算法包括CT 索引構(gòu)建、Exact-G kICT 和Exact-LkICT.實(shí)驗(yàn)軟硬件環(huán)境為：Windows 10 家庭版操作系統(tǒng)，AMD Ryzen 74800H with Radeon Graphics的CPU，主頻2.90 GHz，16 GB 內(nèi)存，1 TB 硬盤；開發(fā)平臺(tái)為JetBrains PyCharm 2020，開發(fā)語言為Python 3.7.

5.2 實(shí)驗(yàn)數(shù)據(jù)集和參數(shù)配置

實(shí)驗(yàn)采用的4 個(gè)真實(shí)數(shù)據(jù)集包括：DBLP，Protein，Email，F(xiàn)acebook.數(shù)據(jù)集統(tǒng)計(jì)信息如表1 所示.

Table 1 The Real Datasets表1 真實(shí)數(shù)據(jù)集

1）DBLP 雙網(wǎng)絡(luò).從DBLP 雙網(wǎng)絡(luò)①https://dblp.uni-trier.de/中提取SIGMOD，VLDB，ICDE，CIKM，EDBT，DASFAA，KDD，ICDM，SDM，WSDM，PAKDD 等11 個(gè)數(shù)據(jù)庫和數(shù)據(jù)挖掘領(lǐng)域會(huì)議.物理圖中結(jié)點(diǎn)之間存在邊則表示2 位作者曾經(jīng)至少共同發(fā)表過1 篇論文；概念圖中的邊表示2 位作者的研究興趣相似度.邊影響力通過使用余弦函數(shù)度量作者間論文關(guān)鍵字相似度獲得.

2）Protein 雙網(wǎng)絡(luò)[17].Protein 雙網(wǎng)絡(luò)中結(jié)點(diǎn)為蛋白質(zhì)對(duì)應(yīng)基因.物理圖中邊表示2 個(gè)基因共調(diào)控關(guān)系.概念圖中邊表示基因與高血壓復(fù)雜疾病的遺傳交互關(guān)系，邊影響力表示統(tǒng)計(jì)顯著值.

3）Email 雙網(wǎng)絡(luò)[43].Email 雙網(wǎng)絡(luò)根據(jù)研究機(jī)構(gòu)電子郵件數(shù)據(jù)構(gòu)建.結(jié)點(diǎn)表示電子郵件用戶，物理圖中邊表示2 個(gè)用戶間發(fā)送過郵件，概念圖中邊表示2個(gè)用戶屬于相同部門.邊影響力表示2 個(gè)用戶屬于共同的部門數(shù)量與總部門數(shù)量的比值.

4）Facebook 雙網(wǎng)絡(luò)[43].Facebook 雙網(wǎng)絡(luò)中結(jié)點(diǎn)表示用戶.物理圖中邊表示2 個(gè)用戶具有相同的政治背景，概念圖中邊表示2 個(gè)用戶具有相似的愛好.邊影響力表示興趣愛好的相似度.

表1 中ktmax表示該數(shù)據(jù)集的最大k-truss 值.由于k-ICT 的正值性有可能出現(xiàn)ktmax與最終選取k值相差過大的情況.雙網(wǎng)絡(luò)根據(jù)各個(gè)數(shù)據(jù)集ktmax值的不同并結(jié)合實(shí)際情況，在實(shí)驗(yàn)中對(duì)于DBLP 數(shù)據(jù)集設(shè)置參數(shù)k值取值范圍為 {3,5,7,9,11}，F(xiàn)acebook 數(shù)據(jù)集的k值取值范圍為{3,5,7,9}，Protein 數(shù)據(jù)集的k值取值范圍為 {3,5,7,9}，Email 數(shù)據(jù)集的k值取值范圍為{5,10,15,20,25}.對(duì)于參數(shù)r，實(shí)驗(yàn)取值范圍為 {5,10,15,20,25}.對(duì)于算法Exact-LkICT 中的子圖規(guī)模擴(kuò)展值 δ設(shè)置為2，本次實(shí)驗(yàn)中 δ不作為參數(shù).

5.3 算法性能分析

本節(jié)主要評(píng)估CT 索引的性能以及k-ICT 子圖發(fā)現(xiàn)算法的效率和可擴(kuò)展性.

5.3.1 CT 索引性能分析

本節(jié)主要評(píng)估CT 索引占用內(nèi)存大小和構(gòu)建CT索引的時(shí)間開銷.

首先，圖6 展示了CT 索引在不同數(shù)據(jù)集上的內(nèi)存大小，同時(shí)給出了與數(shù)據(jù)集對(duì)應(yīng)雙網(wǎng)絡(luò)和概念圖占用索引大小的比較.通過圖6 可以看出，CT 索引占用內(nèi)存要小于雙網(wǎng)絡(luò)占用內(nèi)存，而且只稍稍大于概念圖占用內(nèi)存.這是因?yàn)镃T 索引的概要圖結(jié)構(gòu)規(guī)模非常小，而且每個(gè)超節(jié)點(diǎn)對(duì)應(yīng)雙網(wǎng)絡(luò)概念圖中邊的劃分中的一個(gè)子集，而所有超節(jié)點(diǎn)剛好對(duì)應(yīng)概念圖中的所有邊，因此占用內(nèi)存主要受概念圖大小的影響，在空間上非常緊湊、沒有冗余.

Fig.6 Memory usage of CT index on different datasets圖6 CT 索引在不同數(shù)據(jù)集上內(nèi)存占用

其次，圖7 展示了在不同數(shù)據(jù)集上CT 索引的構(gòu)建時(shí)間.并且在相同數(shù)據(jù)集中給出了CT 索引構(gòu)建的主要構(gòu)成部分，邊CT 數(shù)的CT 分解算法運(yùn)行時(shí)間的比較.從圖7 中可以看出，構(gòu)建CT 索引的時(shí)間主要花費(fèi)在CT 分解上.因?yàn)镃T 分解算法不僅要計(jì)算概念圖中邊的支持度，同時(shí)還要保證子圖在物理圖中連通，因此較為耗時(shí).一旦求得概念圖中邊的CT 數(shù)，CT 構(gòu)建算法中的后續(xù)部分僅需對(duì)概念圖中的三角形進(jìn)行遍歷，就能求出概要圖中超節(jié)點(diǎn)對(duì)應(yīng)的等價(jià)類以及構(gòu)建超節(jié)點(diǎn)之間的超邊.

Fig.7 CT index construction time on different datasets圖7 CT 索引在不同數(shù)據(jù)集上的構(gòu)建時(shí)間

5.3.2 top-r最大影響力k-ICT 子圖發(fā)現(xiàn)算法效率

本節(jié)主要評(píng)估算法Exact-G kICT 和算法Exact-LkICT 發(fā)現(xiàn)top-r最大影響力k-ICT 子圖的效率.

首先，圖8 展示了算法Exact-G kICT 和算法Exact-LkICT 在固定r值的情況下隨k值變化的運(yùn)行時(shí)間.從圖8 中可以看出，在所有的真實(shí)數(shù)據(jù)集中，算法Exact-LkICT 比算法Exact-G kICT 運(yùn)行速度更快.造成這種現(xiàn)象的原因是算法Exact-LkICT 在發(fā)現(xiàn)top-r最大影響力k-ICT 子圖時(shí)，不需要使用全局k-CT 子圖，而只需知曉結(jié)果子圖的大小，因此運(yùn)行速度更快.這種現(xiàn)象在k值較小時(shí)更為明顯，算法Exact-LkICT 要比Exact-GkICT 快至少1 個(gè)數(shù)量級(jí).反觀算法Exact-GkICT，每次都需要從全局k-CT 子圖中刪除邊或點(diǎn)來獲得最終結(jié)果.對(duì)于算法Exact-G kICT，在一些數(shù)據(jù)集上的運(yùn)行速度隨k的增加而變快，原因是全局k-CT子圖的規(guī)模隨k的增加而變小.對(duì)于算法Exact-LkICT，其運(yùn)行時(shí)間隨k的增加略微增加，原因是隨k的增加結(jié)果子圖規(guī)模增大.

Fig.8 The runtime with varying k in different real datasets圖8 不同真實(shí)數(shù)據(jù)集中隨k 值變化的運(yùn)行時(shí)間

其次，圖9 展示了算法Exact-G kICT 和算法Exact-LkICT 在固定k值的情況下隨r值變化的運(yùn)行時(shí)間.從圖9 能夠看出，在所有真實(shí)數(shù)據(jù)集中，算法Exact-LkICT 的運(yùn)行時(shí)間要遠(yuǎn)低于算法Exact-G kICT 的運(yùn)行時(shí)間.原因與圖8 中實(shí)驗(yàn)分析一致.但是，對(duì)于算法Exact-G kICT，其運(yùn)行時(shí)間隨r值變化基本沒有變化.原因是在k值固定的情況下k-CT 子圖規(guī)模未發(fā)生變化，而且算法Exact-G kICT 發(fā)現(xiàn)k-ICT 子圖的影響力值由小逐漸變大，算法最后才能得到最大影響力的子圖.為獲得top-r個(gè)最大影響力子圖仍需運(yùn)行整個(gè)算法，r值的變化只能引起輸出結(jié)果數(shù)量的變化，運(yùn)行時(shí)間變化可忽略不計(jì).對(duì)于算法Exact-LkICT，其運(yùn)行時(shí)間隨r值增加而增加，原因是需要從規(guī)模更大的局部子圖中來發(fā)現(xiàn)更多的結(jié)果子圖，因此運(yùn)行時(shí)間更長，但總運(yùn)行時(shí)間仍遠(yuǎn)小于算法Exact-G kICT.

Fig.9 The runtime with varying r in different real datasets圖9 不同真實(shí)數(shù)據(jù)集中隨r 值變化的運(yùn)行時(shí)間

5.4 算法有效性分析

從k-ICT 子圖定義能夠發(fā)現(xiàn)k-ICT 子圖包含于k-CT 子圖中，k-CT 子圖可以被視為k-ICT 子圖的候選集合.相較k-CT 子圖，最大影響力k-ICT 子圖結(jié)構(gòu)更加緊密且規(guī)模更小，能夠表示k-CT 子圖中最核心且重要的子圖區(qū)域.

本節(jié)使用概念圖直徑和圖中結(jié)點(diǎn)數(shù)量來比較k-ICT 子圖和k-CT 子圖模型的緊密性.其中子圖直徑定義為圖中任意2 個(gè)結(jié)點(diǎn)間最短路徑中的最大值，即，其中distance(u,v)表示結(jié)點(diǎn)u和v在圖中的最短距離.子圖直徑值越小說明圖越緊密.另外，使用圖結(jié)點(diǎn)數(shù)量 |V|表示子圖規(guī)模，結(jié)點(diǎn)數(shù)量越少說明子圖規(guī)模越小.

圖10 展示了k-ICT 子圖和k-CT 子圖在不同真實(shí)雙網(wǎng)絡(luò)數(shù)據(jù)集中直徑大小的比較.總體來看，對(duì)于不同的k值，k-ICT 子圖直徑要小于k-CT 子圖直徑，原因是k-ICT 子圖雖然結(jié)構(gòu)約束和k-CT 子圖一樣強(qiáng)，但是規(guī)模更小.k-ICT 為k-CT 的子圖，表示k-CT 子圖中影響力最大且更為核心的區(qū)域，因此結(jié)點(diǎn)之間的距離更近、直徑更小.另外，從圖10 中能夠發(fā)現(xiàn)，對(duì)于k-CT 子圖，當(dāng)k值較小時(shí)，子圖直徑有可能更小，這是因?yàn)閳D中有許多直徑非常小的k-CT 子圖，在計(jì)算直徑平均值時(shí)，降低了規(guī)模較大k-CT 子圖的直徑.隨著k值變大，這些小規(guī)模k-CT 子圖被不斷過濾掉，因此子圖直徑反而變大.但是，當(dāng)k值繼續(xù)增大時(shí)，子圖約束更強(qiáng)，直徑又開始變小.對(duì)于k-ICT 子圖，其隨k值變化直徑變化并不明顯，這是因?yàn)閗-ICT 子圖始終保持較小規(guī)模.

Fig.10 Subgraph diameter in different real dual networks圖10 不同真實(shí)雙網(wǎng)絡(luò)中子圖直徑

圖11 展示了不同真實(shí)雙網(wǎng)絡(luò)中k-CT 子圖和k-ICT 子圖在不同k值下的規(guī)模.從圖11 中能夠看出，k-ICT 子圖規(guī)模整體小于k-CT 子圖規(guī)模，只有在DBLP 雙網(wǎng)絡(luò)中兩者規(guī)模相近.原因是k-ICT 子圖為k-CT 子圖中影響力最大且同樣滿足結(jié)構(gòu)約束的子圖，所以規(guī)模更小.在DBLP 雙網(wǎng)絡(luò)中k-CT 子圖規(guī)模本身較小，因此和k-ICT 子圖規(guī)模相差并不明顯，但是對(duì)于其他雙網(wǎng)絡(luò)規(guī)模差距非常明顯.對(duì)于k-CT 子圖，DBLP 和Email 雙網(wǎng)絡(luò)中子圖平均規(guī)模隨k值增大.Protein 雙網(wǎng)絡(luò)規(guī)模呈先增大后減小趨勢(shì)，原因是隨k值增大，過濾掉規(guī)模較小的k-CT 子圖，因此子圖規(guī)模更大.但是當(dāng)k值更大時(shí)，當(dāng)前規(guī)模大的子圖被打散為許多小的子圖，因此規(guī)模變小.而Facebook 雙網(wǎng)絡(luò)則始終存在一個(gè)很大的k-CT 子圖，總之，與雙網(wǎng)絡(luò)的結(jié)構(gòu)分布有關(guān).對(duì)于k-ICT 子圖，子圖規(guī)模隨k值增大而增加，同時(shí)子圖中頂點(diǎn)數(shù)量與k值大小在相同數(shù)量級(jí).原因是k-ICT 子圖在子圖影響力的約束下定義結(jié)構(gòu)上的極大性，最大影響力k-ICT 子圖規(guī)模往往很小，但需要包含至少k個(gè)結(jié)點(diǎn).

Fig.11 Subgraph scale in different real dual networks圖11 不同真實(shí)雙網(wǎng)絡(luò)中子圖規(guī)模

5.5 案例分析

圖12 展示了Protein 雙網(wǎng)絡(luò)中top-1 最大影響力9-ICT 子圖.Protein 雙網(wǎng)絡(luò)概念圖中邊表示2 個(gè)基因與高血壓疾病的交互顯著程度，邊影響力越大說明具有越強(qiáng)的統(tǒng)計(jì)顯著性；物理圖中邊表示2 個(gè)基因在蛋白質(zhì)交互網(wǎng)絡(luò)中具有真實(shí)的物理共調(diào)控作用.圖12 中子圖的概念圖不僅稠密而且具有很高的邊影響力，并且在物理圖中連通，說明該子圖與高血壓疾病具有顯著關(guān)聯(lián)關(guān)系.例如，文獻(xiàn)[44]中報(bào)道基因STK24（又名MST3）能夠調(diào)節(jié)血液中鈉離子的濃度，這與鈉離子表達(dá)增強(qiáng)引起的遺傳性高血壓具有直接關(guān)系.文獻(xiàn)[45]中報(bào)道STRN 基因多態(tài)性變異與血壓正常和高血壓患者的鹽敏感性血壓相關(guān).PPP2 基因族（PPP2R1A 和PPP2CA）[46]是人類心臟功能的子單元，而心臟功能對(duì)血壓有直接影響.文獻(xiàn)[47]中報(bào)道基因CTTNBP2 與血壓的遺傳因素有直接關(guān)系.而且STK24，STRN，STRN3，PDCD10 等基因都在相同的控制心血管的功能團(tuán)中[48].因此，本文發(fā)現(xiàn)的Protein 雙網(wǎng)絡(luò)中真實(shí)結(jié)果具有非常強(qiáng)的生物學(xué)意義.另外，k-ICT 子圖規(guī)模較k-CT 子圖更小，具有更強(qiáng)的可解釋性.

6 結(jié)論

本文提出一種雙網(wǎng)絡(luò)中k-ICT 子圖模型，該模型利用子圖中最小邊影響力定義子圖影響力具有更強(qiáng)魯棒性.影響力最大k-ICT 子圖能夠有效反映子圖在網(wǎng)絡(luò)中的重要性且規(guī)模更小同時(shí)具備更強(qiáng)解釋性.與當(dāng)前k-truss 和k-CT 模型相比得出，誘導(dǎo)子圖的約束條件使得發(fā)現(xiàn)影響力最大k-ICT 子圖問題為NP-難的.為此，首先提出一種基于概念圖中邊CT 等價(jià)類劃分的CT 索引結(jié)構(gòu)，根據(jù)索引概要圖能夠快速發(fā)現(xiàn)包含所有k-ICT 子圖的候選子圖，避免每次都從整個(gè)雙網(wǎng)絡(luò)中發(fā)現(xiàn)k-ICT 子圖.其次，分別提出基于全局枚舉刪除策略和局部子圖擴(kuò)展策略的精確算法Exact-GkICT 和Exact-LkICT，發(fā)現(xiàn)top-r最大影響力k-ICT子圖.由于Exact-LkICT 算法僅需從影響力較大邊集合構(gòu)成的子圖中發(fā)現(xiàn)滿足條件的結(jié)果，因此當(dāng)r值較小時(shí)運(yùn)行效率更高.最后，在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了本文的模型和算法的高效性和有效性.未來工作將設(shè)計(jì)更高效的近似算法來發(fā)現(xiàn)近似k-ICT 子圖.

作者貢獻(xiàn)聲明：李源負(fù)責(zé)算法設(shè)計(jì)和論文撰寫；楊森負(fù)責(zé)算法編寫和實(shí)驗(yàn)；孫晶負(fù)責(zé)實(shí)驗(yàn)設(shè)計(jì)和論文撰寫；趙會(huì)群負(fù)責(zé)論文框架設(shè)計(jì)和論文修改；王國仁負(fù)責(zé)論文框架設(shè)計(jì).