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