丁云平

（四川大學計算機學院，成都610065）

0 引言

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

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

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

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

1 相關概念與定義

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

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

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

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

其取值范圍若為（1，+∞），則 u，v正相關，若為 1，則 u，v相互獨立，若為[0，1）則 u，v負相關。

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

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

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

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

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

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

（1）直接影響

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

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

（2）間接影響

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

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

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

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

3 實驗分析

3.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)集相關統(tǒng)計信息

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

3.2 實驗結果與分析

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

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

圖2 運行時間

4 結語

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