丁云平

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

信息網(wǎng)絡(luò)(Information Network)是 Jiawei Han、Philip S.Yu等在EDBT 2009和SIGMOD 2010的Tutorial上正式提出和倡導(dǎo)的新研究方向，是對(duì)現(xiàn)實(shí)空間中海量、多維、復(fù)雜結(jié)構(gòu)數(shù)據(jù)和問題更具一般性的抽象[1，2]。近年來，信息網(wǎng)絡(luò)的研究被廣泛應(yīng)用于通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。

銷售信息網(wǎng)絡(luò)作為信息網(wǎng)絡(luò)的一種，將商品的銷售關(guān)系用網(wǎng)絡(luò)圖的形式進(jìn)行表示，每個(gè)商品節(jié)點(diǎn)有銷售量等屬性，連接節(jié)點(diǎn)的邊表示商品的共售關(guān)系。通過對(duì)銷售信息進(jìn)行網(wǎng)絡(luò)建模，用戶能夠從多角度、多層次的觀察和分析基于圖的復(fù)雜主題對(duì)象，從而實(shí)時(shí)、直觀地發(fā)現(xiàn)商品的銷售情況，制定相應(yīng)的銷售策略。如圖1所示。

圖1 由傳統(tǒng)銷售項(xiàng)目集到新一代基于信息網(wǎng)絡(luò)的銷售網(wǎng)絡(luò)

社團(tuán)結(jié)構(gòu)是信息網(wǎng)絡(luò)的一個(gè)重要特性，在信息網(wǎng)絡(luò)研究中是一熱點(diǎn)問題[3-5]。社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中的頂點(diǎn)可以分成組，組內(nèi)節(jié)點(diǎn)連接比較稠密，而組間頂點(diǎn)連接比較稀疏。由于社團(tuán)結(jié)構(gòu)廣泛地存在于實(shí)際網(wǎng)絡(luò)當(dāng)中，是網(wǎng)絡(luò)的重要性質(zhì)，因此對(duì)社團(tuán)結(jié)構(gòu)的研究是了解網(wǎng)絡(luò)結(jié)構(gòu)和功能的重要途徑。近年來關(guān)于社團(tuán)的研究和相關(guān)的算法很多，但是這些研究?jī)H考慮了網(wǎng)絡(luò)本身的拓?fù)浣Y(jié)構(gòu)，并不考慮現(xiàn)實(shí)世界中的網(wǎng)絡(luò)具有的顯式或隱式信息，不適用于銷售信息網(wǎng)絡(luò)的研究。

1 相關(guān)概念與定義

為了更好的描述本文提出的算法，本節(jié)首先對(duì)相關(guān)概念進(jìn)行數(shù)學(xué)定義。

定義1銷售信息網(wǎng)絡(luò)在無向圖G=(V,E,W,N)中，V和E分別表示節(jié)點(diǎn)集和邊集，W為邊的權(quán)重，表示與之相連的兩個(gè)商品節(jié)點(diǎn)共售的次數(shù)，N為節(jié)點(diǎn)的屬性，表示節(jié)點(diǎn)的銷量。表示節(jié)點(diǎn)的數(shù)量，表示邊的數(shù)量。

定義2節(jié)點(diǎn)v的鄰居對(duì)于給定節(jié)點(diǎn)v，其鄰居節(jié)點(diǎn)集合NG(v)={u:(u,v)∈E}，dG(v)表示節(jié)點(diǎn)v的度。

定義3相關(guān)系數(shù)為了判斷兩個(gè)商品的相關(guān)性，引入相關(guān)系數(shù)（corru,v）這一概念，通過該參數(shù)來度量商品u，v的相關(guān)性：

其取值范圍若為（1，+∞），則 u，v正相關(guān)，若為 1，則 u，v相互獨(dú)立，若為[0，1）則 u，v負(fù)相關(guān)。

定義4杰卡德距離給定無向圖G=(V,E,W,N)，節(jié)點(diǎn)u,v的杰卡德距離定義為：

考慮節(jié)點(diǎn)的相關(guān)性，初始的杰卡德距離為：

2 基于相關(guān)性的社團(tuán)發(fā)現(xiàn)算法

傳統(tǒng)的社團(tuán)發(fā)現(xiàn)只考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，即同一個(gè)社團(tuán)內(nèi)部節(jié)點(diǎn)盡可能緊密、不同社團(tuán)的節(jié)點(diǎn)之間盡可能稀疏，這種思想不能很好地反映現(xiàn)實(shí)世界的真實(shí)現(xiàn)象。例如，商品ABCDE只要有一次被購買，兩兩之間就會(huì)存在一條邊，但真實(shí)情況是ABCD經(jīng)常被一起購買，E只有一次和它們一起購買，如果采用傳統(tǒng)的社團(tuán)發(fā)現(xiàn)算法，只考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，挖掘出來的社團(tuán)很可能是ABCDE，這與真實(shí)情況相悖，本文通過分析商品節(jié)點(diǎn)間的相關(guān)性解決這個(gè)問題。

為了解決傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法中存在的弊端，在本節(jié)中，本文在文獻(xiàn)[6]的基礎(chǔ)上，引入銷售信息網(wǎng)絡(luò)自身的信息，提出了基于節(jié)點(diǎn)相關(guān)性的距離動(dòng)力學(xué)社團(tuán)發(fā)現(xiàn)算法。銷售信息網(wǎng)絡(luò)的每條邊與初始距離d相關(guān)聯(lián)，該距離受到兩種交互模型和自身信息的影響，距離d動(dòng)態(tài)地變化，增大或者減少，最后距離收斂（距離為1或者0）。最后移除距離為1的鏈接，銷售信息網(wǎng)絡(luò)將會(huì)被劃分成若干不同的商品社團(tuán)。

銷售信息網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)，與其鄰居在交互過程中，不同的鄰居會(huì)對(duì)其產(chǎn)生不同的影響。設(shè)e={u,v}∈E是節(jié)點(diǎn)u和v之間的一條連邊，由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)自身信息的作用，會(huì)有兩種不同的情況會(huì)影響兩個(gè)節(jié)點(diǎn)之間的距離d(u,v)。（1）直接影響；（2）間接影響。

（1）直接影響

節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的距離d(u,v)明顯地受到兩個(gè)直接連接節(jié)點(diǎn)u和v的影響，但不同于社交網(wǎng)絡(luò)，直接鄰居的影響是積極的。在銷售信息網(wǎng)絡(luò)中，直接鄰居的影響可能是消極的。本文通過節(jié)點(diǎn)之間的相關(guān)性描述兩個(gè)節(jié)點(diǎn)之間的影響是積極的還是消極的。如果兩個(gè)節(jié)點(diǎn)是負(fù)相關(guān)的，那么它們之間的距離直接為1（1為兩個(gè)節(jié)點(diǎn)的最大距離），如果兩個(gè)節(jié)點(diǎn)是正相關(guān)的，那么直接連接會(huì)導(dǎo)致距離d(u,v)的減小，公式如下:

其中分母dG(.)為節(jié)點(diǎn)的度，f(.)是一個(gè)耦合函數(shù)（本文采用sin），1-d(u,v))表示u和v之間的關(guān)聯(lián)度，兩個(gè)節(jié)點(diǎn)之間的關(guān)聯(lián)度越高，他們之間的影響越大。是歸一化因子，用于考慮不同的連接節(jié)點(diǎn)之間的不同影響，即與度較小的商品節(jié)點(diǎn)相比，具有較大度的商品節(jié)點(diǎn)更難受到影響。

（2）間接影響

兩個(gè)商品節(jié)點(diǎn)間的距離同樣會(huì)受到其鄰居的影響，為了定義鄰居對(duì)距離的正面或負(fù)面影響，本文提出了一種基于相關(guān)性的啟發(fā)式策略，基本思想是分析鄰居節(jié)點(diǎn)x與u，v的相關(guān)性。如果鄰居和節(jié)點(diǎn)u，v都是正相關(guān)的，則該鄰居會(huì)吸引兩個(gè)節(jié)點(diǎn)靠近，從而使距離減小，如果鄰居和其中一個(gè)是負(fù)相關(guān)的，另外一個(gè)是正相關(guān)的，則會(huì)導(dǎo)致兩個(gè)節(jié)點(diǎn)之間的距離增大，如果和其中兩個(gè)節(jié)點(diǎn)都是負(fù)相關(guān)的，則認(rèn)為該鄰居會(huì)使兩個(gè)節(jié)點(diǎn)的距離減小。如果鄰居節(jié)點(diǎn)和其中一個(gè)或兩個(gè)是不相關(guān)的，則認(rèn)為該鄰居節(jié)點(diǎn)不會(huì)對(duì)其距離產(chǎn)生影響，公式如下：

這里采用的歸一化因子不同于公式（1），表示共售比重大的鄰居對(duì)節(jié)點(diǎn)的影響更大。

最后距離動(dòng)態(tài)變化公式為：

算法偽代碼如算法1所示：

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

在這個(gè)實(shí)驗(yàn)中，一共使用了四個(gè)數(shù)據(jù)集。包括真實(shí)數(shù)據(jù)集amazon0302、chess和mushroom，以及IBM模擬數(shù)據(jù)生成器生成的模擬數(shù)據(jù)集T40110D100K。

表1 實(shí)驗(yàn)數(shù)據(jù)集相關(guān)統(tǒng)計(jì)信息

4組不同數(shù)據(jù)集節(jié)點(diǎn)度的分布情況如圖1所示。

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

為了證明CCD算法的有效性，與文獻(xiàn)[6]提出的算法Attractor進(jìn)行對(duì)比，該算法在設(shè)計(jì)上只考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。實(shí)驗(yàn)結(jié)果如圖2所示，從圖中可以看出，本文提出的算法在四個(gè)數(shù)據(jù)集上均具有良好的表現(xiàn)，且在數(shù)據(jù)較大時(shí)，本文提出的算法在運(yùn)行時(shí)間上更具優(yōu)勢(shì)。這是因?yàn)楸疚奶岢龅乃惴ㄔ诳紤]商品節(jié)點(diǎn)相關(guān)性后，可以加快距離的收斂，從而減少算法運(yùn)行時(shí)間。

圖1 4組數(shù)據(jù)節(jié)點(diǎn)度分布

圖2 運(yùn)行時(shí)間

4 結(jié)語

本文提出基于相關(guān)性的距離動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)算法，用于發(fā)現(xiàn)銷售信息網(wǎng)絡(luò)中更符合一般經(jīng)驗(yàn)的商品社團(tuán)。在兩種距離交互模型的影響下，考慮商品節(jié)點(diǎn)之間的相關(guān)性，節(jié)點(diǎn)間的距離逐漸收斂為0或1，通過移除距離為1的邊，從而動(dòng)態(tài)地劃分商品社團(tuán)。相比于原始的Attractor算法，本文的算法能夠較快地使網(wǎng)絡(luò)之間的距離收斂，從而減少算法的運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果顯示該算法具有較好的有效性。下一步將主要研究如何如何衡量發(fā)現(xiàn)的商品社團(tuán)的好壞。