近日，我校數(shù)據(jù)科學(xué)與計算機學(xué)院胡延慶副教授、馬嘯教授與孫嘉辰博士生、謝家榮博士后等在國際知名雜志《自然·通訊》（Nature Communications）上發(fā)表了題為“Revealing the predictability of intrinsic structure in complex networks”的研究論文。該研究首次發(fā)現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)可預(yù)測性與網(wǎng)絡(luò)結(jié)構(gòu)的最短壓縮比特串長度呈線性關(guān)系，該理論可以在不依賴于任何結(jié)構(gòu)預(yù)測算法的情況下，給出網(wǎng)絡(luò)結(jié)構(gòu)可預(yù)測性的極限。
復(fù)雜網(wǎng)絡(luò)作為一種通用的數(shù)據(jù)表示形式，廣泛存在于生物學(xué)、推薦系統(tǒng)、社交媒體等各個領(lǐng)域。它主要用以表示復(fù)雜系統(tǒng)內(nèi)，元素之間不能用簡單的數(shù)學(xué)來很好地描述的相互作用關(guān)系。復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測技術(shù)在很多領(lǐng)域有廣泛的應(yīng)用。例如，預(yù)測細(xì)胞內(nèi)的蛋白質(zhì)之間或者蛋白質(zhì)與藥物的相互作用關(guān)系可以指導(dǎo)更精確的生物學(xué)實驗，減少實驗成本和時間。由于自然界的復(fù)雜網(wǎng)絡(luò)形成過程非常復(fù)雜，其結(jié)構(gòu)的預(yù)測極具挑戰(zhàn)性。近年來學(xué)術(shù)界提出了許多機器學(xué)習(xí)方法等相關(guān)的預(yù)測算法，并致力于提高算法的性能。然而，始終缺乏對于網(wǎng)絡(luò)本身可預(yù)測性（最大可預(yù)測極限）的基本理解。其難點在于：網(wǎng)絡(luò)在形成過程中存在著十分復(fù)雜、未知的內(nèi)外部因素。同時，網(wǎng)絡(luò)形成后的結(jié)構(gòu)極其復(fù)雜，體積龐大，短程反饋回路眾多，導(dǎo)致一直沒有合適的數(shù)學(xué)理論來理解網(wǎng)絡(luò)結(jié)構(gòu)可預(yù)測性的內(nèi)在本質(zhì)。
在本研究工作中，該團隊利用信息論和統(tǒng)計物理兩個領(lǐng)域中熵的相關(guān)理論，對網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測極限進(jìn)行了研究。直觀地說，一個可以僅用幾個詞描述的網(wǎng)絡(luò)結(jié)構(gòu)意味著它很簡單，其邊也很容易預(yù)測。例如二維晶格或一維鏈狀結(jié)構(gòu)。相反，如果一個網(wǎng)絡(luò)需要很長的語言才能描述清楚，那么它應(yīng)該具有非常復(fù)雜的結(jié)構(gòu)，其結(jié)構(gòu)很難預(yù)測。在計算機領(lǐng)域，任何網(wǎng)絡(luò)的結(jié)構(gòu)都可以被編碼成二進(jìn)制字符串。這啟發(fā)了團隊探尋最短二進(jìn)制編碼字符串長度，也就是熵，和可預(yù)測性之間的關(guān)系。
通過研究，該團隊發(fā)現(xiàn)來自不同領(lǐng)域，很多大小不一的網(wǎng)絡(luò)，其結(jié)構(gòu)的最短壓縮長度和可預(yù)測性之間存在一個普遍的線性關(guān)系?；谙戕r(nóng)信源編碼定理，該團隊在隨機網(wǎng)絡(luò)上證明了這種線性關(guān)系。
進(jìn)一步，利用這一線性關(guān)系，該團隊推導(dǎo)出網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測算法的性能上界，揭示出包括機器學(xué)習(xí)在內(nèi)的預(yù)測算法性能尚存在多大的提升空間。因此，該性能界可用于指導(dǎo)未來在線商業(yè)推薦系統(tǒng)、蛋白質(zhì)相互作用探測等場景中的算法設(shè)計。另外，該理論的一個有趣的用途是，可以實現(xiàn)在無需任何預(yù)測算法的情況下，通過網(wǎng)絡(luò)結(jié)構(gòu)壓縮數(shù)據(jù)大小來估計一個網(wǎng)絡(luò)數(shù)據(jù)集的商業(yè)價值。
該研究受國家自然科學(xué)基金面上項目No. 61773412, U1911201等項目支持。
