基于內部邊的群體軟件開發中的項目推薦方法

丁 沂 ，李 兵 ，程 璨 ，張 迪

DING Yi1,4,LI Bing2,3,CHENG Can2,ZHANG Di2

1.武漢大學 計算機學院&軟件工程國家重點實驗室，武漢 430072

2.武漢大學 國際軟件學院&軟件工程國家重點實驗室，武漢 430072

3.武漢大學 復雜網絡研究中心，武漢 430072

4.武漢軟件工程職業學院 計算機學院，武漢 430205

1.State Key Lab of Software Engineering&School of Computer,Wuhan University,Wuhan 430072,China

2.International School of Software&State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072,China

3.Research Center of Complex Network,Wuhan University,Wuhan 430072,China

4.School of Computer,Wuhan Vocational College of Software and Engineering,Wuhan 430205,China

1 引言

推薦系統幫助用戶在缺少經驗，無法全面考慮數據時發現有用的信息和制定決策。這類系統采用計算機科學和工程學方法，根據用戶潛在的、模糊的需求，向用戶提供現實的、明確的信息或建議[1]。軟件工程推薦系統（recommendation systems for software engineering）的出現，給軟件開發的各種活動帶來極大便利。它為軟件開發者提供大量信息，指導他們進行各種開發活動，幫助他們修改潛在的問題；幫助軟件管理者進行決策時過濾信息[2]。

當前，對軟件生態系統的歷史和實證研究已經成為一個快速發展的研究領域。根據軟件生態系統的定義[3]，這種生態系統一個重要特征是：由大量軟件項目組成，這些項目被一個用戶和貢獻者社區所共享。GNOME項目[4]就是開源軟件生態系統和群體軟件開發的一個典型例子。GNOME項目是一個完整的、由多個軟件項目組成的軟件桌面環境，該項目由來自全球范圍內的開發者組成的開發者社區負責開發。開源軟件生態系統很容易形成協作社會網絡，開源項目推薦系統能夠幫助用戶以方面快捷的方式找到合適的相關項目。GNOME項目的用戶主要包括活躍用戶和較活躍用戶，活躍用戶通常要比較活躍用戶的貢獻更大。無論是活躍用戶還是較活躍用戶都能夠從項目推薦系統中獲得收益。對于活躍用戶，項目推薦系統能幫助他們尋找感興趣的新項目，從而獲得更多的商業機會；對于較活躍用戶，項目推薦系統也能幫助他們比較容易地找到新的合作機會和相關項目。

大量真實的復雜網絡具有自然的二分結構，可以使用二分網絡對它們建模。二分網絡包含兩類不同節點，鏈接僅僅存在于不同類型的節點之間，同類節點之間沒有鏈接，例如：用戶和產品之間由于購買關系所形成的用戶-產品二分網絡以及互聯網文檔提供者和提供的文檔之間所形成的提供者-文檔二分網絡等。本文首先從GNOME數據集中提取開發者和項目的關系構建開發者-項目二分網絡，其中一類節點代表項目開發者，另外一類節點代表開源項目，兩類不同節點之間的連邊代表開發者參與過該項目的開發，利用二分網絡的結構和網絡分析技術，評價一個項目是否與開發者相關，并最終決定該項目是否值得推薦。

本文的主要貢獻可概括如下：

（1）構建開發者-項目二分網絡，利用不同的局部相似性指標通過加權投影將二分網絡轉換為單模網絡，采用一種基于內部邊的鏈路預測方法對開發者進行項目推薦。

（2）在不同的局部相似性指標下將基于內部邊的推薦方法與協同過濾方法進行了對比，驗證了該方法的有效性。

2 相關工作

推薦系統在用戶面臨信息過載或無法明確描述需求的情況下，根據用戶的歷史行為和偏好主動為用戶推薦感興趣的內容，包括網頁、標簽、產品、新聞、音樂和電影等。推薦系統使用的方法主要包括：基于內容的方法、基于近鄰的方法、基于匹配的方法、協同過濾方法和機器學習方法等。在軟件工程推薦系統領域Ferdian等[5]從GitHub數據集中提取項目-項目網絡和開發者協作網絡，發現這兩個網絡具有較低的平均距離和無標度特征。Surian等[6]利用SourceForge數據集進行開發者協作分析，從中提取拓撲結構，發現SourceForge網絡具有小世界效應。Antonio等[7]對GitHub網絡進行結構分析，發現地理位置相近的用戶更有可能共同參與一個項目的開發。Zimmermann等[8]通過挖掘軟件版本歷史信息，預測代碼變更、不完整的代碼修改而產生的錯誤以及軟件內部不易察覺的耦合關系。Mockus等[9]利用版本變更信息量化開發者的經驗水平，開發了一個工具為人們推薦需要的專家。McDonald等[10]提出了一個專家定位框架，減輕開發者的工作強度，為開發提供各種意見。Surian等[11]利用開發者開發過的項目所使用的編程語言和類別，結合開發者、項目的關系構建開發者合作網絡，使用隨機游走算法，實現開發者推薦。楊習輝等[12]以SourceForge.Net社區為研究對象，構建開發者-項目關聯網絡，結合開發者技能和項目需求關聯度，為開發者推薦最適合的項目。何鵬等[13]根據開發者的歷史開發信息，結合開發者的實踐技能相似性與共同開發者數，為SourceForge.Net社區未曾合作的開發者提供一種同行推薦的方法。

與推薦系統比較相似的問題是二分網絡中的鏈路預測問題，二分網絡中的鏈路預測是指如何通過已知的網絡節點及網絡結構等信息，預測網絡中尚未產生連邊的兩個節點之間產生連接的可能性，既包含對當前網絡未知鏈接的預測，也包含對未來鏈接的預測。推薦系統與二分網絡鏈路預測的主要區別在于：推薦系統關注的是給所有用戶推薦他們可能感興趣的物品，而二分網絡鏈路預測所關注的是未來可能產生多少新的連邊；推薦系統不太關注某一個具體的節點未來會產生多少新的連邊（即：某一個用戶會對多少不同物品感興趣），而這恰恰是鏈路預測所關注的。已有的軟件工程推薦系統大都利用協同過濾、機器學習和開發者-項目屬性匹配的方法進行推薦，本文采用網絡結構和網絡分析技術對開發者進行項目推薦。利用網絡分析方法進行推薦通常都采用基于鏈接預測的技術，很多作者對經典圖的鏈路預測進行了大量研究[14-16]，對二部圖鏈路預測的研究卻相對較少。Huang等[17]將二部圖轉換為經典圖，采用經典圖中的一些拓撲度量指標進行鏈路預測。Benchettara等[18]同樣將二部圖轉換為經典圖，使用機器學習方法進行鏈路預測。在最近的研究中，Xie等[19]用復數作為邊的權重對二分網絡中關系的雙重含義建模，并使用復數表示關系的傳遞。Sherkat等[20]在二分網絡中模擬蟻群尋找食物的過程進行鏈路預測。傳統的鏈路預測方法大都采用節點相似性進行預測，節點相似性可以進一步分為局部相似性（例如：Common neighbors指標、Jaccard指標、Adamic-Adar指標、Resource allocation指標等）和全局相似性（例如：Katz指標、Leicht-Holme-Newman指標、Matrix Forest指標等），這些指標大多數只能用于經典圖，不能直接用于二部圖?？梢岳枚繄D節點之間的相似性，通過單模投影的方法推導出同類節點之間的直接聯系。基于這種思路，Allali等[21]使用內部邊（一種基于鄰居相似性的變體）對二部圖進行鏈路預測。簡單地說，內部邊是當前二部圖中不存在的邊，該邊的加入不改變原二部圖通過單模投影推導出的同類節點之間的聯系，即不會改變投影后同類節點之間的鄰居關系。

3 基本概念

現實世界中，很多復雜網絡具有二分結構，可以用二部圖進行刻畫。二部圖可以形式化描述為：G=(D,U,E)，D和U代表兩組不同類型節點的集合，E是這兩組不同類型節點之間邊的集合，即：(d,u)∈E，d∈D,u∈U。二部圖關鍵一點是連邊僅存在于兩組不同類型的節點之間，同組類型相同節點之間沒有連邊（圖1（a））。在二部圖中，如果兩個節點之間存在連邊，那么這兩個節點互為鄰居關系。由于二部圖的連邊僅僅存在于兩組不同類型的節點之間，二部圖中一個節點的鄰居包含在另一組不同類型的節點集合中。例如在圖1（a）所示的二部圖中，節點d2的鄰居N(d2)=(u2,u3),節點u1的鄰居N(u1)=(d1,d3)。如果將二部圖兩組不同類型節點上下擺放，根據同類節點之間是否存在共同的鄰居，可以通過向下或向上投影的方法，推導出同類節點之間的聯系。通過向下投影，二部圖G=(D,U,E)可以轉化為GD-PROJ=(D,ED)（圖1（b））；同理，通過向上投影二部圖G=(D,U,E)可以轉化為GU-PROJ=(U,EU)（圖1（c））。

盡管二部圖投影的方法非常有效并被廣泛應用，但是這種構造方式也損失了很多信息，而原始二部圖的結構則包含了這些信息。例如，在投影過程中并沒有考慮兩個節點共同鄰居的數量，只考慮了兩個節點是否有共同鄰居。通過給投影賦予權重，可以在投影過程中保留這類信息，關于加權投影內容將在本文后面的投影算法部分進行介紹。采用內部邊的方法對開發者進行項目推薦有兩個重要的概念：導出邊和內部邊。

導出邊的定義：給定一個二部圖G=(D,U,E)，二部圖任一節點對(di,ui)的導出邊D-PROJ(di,ui)={di}×N(ui)={(di,dj),dj∈N(ui)}。在圖1中，(d1,u2)的導出邊D-PROJ(d1,u2)包括(d1,d2),(d1,d3)和(d1,d4)。

內部邊的定義：給定一個二部圖G=(D,U,E)，向二部圖中添加一條邊(di,ui)，生成二部圖G′=(D,U,E′)。如果GD-PROJ=G′D-PROJ，那么這條邊(di,ui)就是內部邊。簡單講，內部邊是當前二部圖中不存在的邊的子集，即要預測的邊，這條邊的加入不會改變原始二部圖投影后的結果。在圖1中，將(d2,u1)加入到二部圖，(d2,u1)的導出邊為(d2,d1)和(d2,d3)，然而(d2,d1)在原二部圖的投影圖中卻不存在，因此(d2,u1)不是內部邊；將(d2,u4)加入到二部圖，(d2,u4)的導出邊為(d2,d3)、(d2,d4)和(d2,d5)，這些邊在原二部圖的投影中已經存在，該邊的加入并沒有改變原二部圖投影結果，因此(d2,u4)是內部邊。

4 基于內部邊的項目推薦方法

4.1 構建開發者-項目二分網絡

本文方法首先要構造一個二部圖，從數據集中提取開發者ID和項目ID以及開發者參與過哪些項目，從而識別兩類不同的節點以及它們之間的關系，底部節點代表開發者，頂部節點代表項目，如果開發者參與開發過某個項目，那么它們之間就連邊，從而構建開發者-項目二分網絡：G=(Developers,Items,Joins)，其中Developers為開發者集合，Items為項目集合，Joins為開發者和項目關系集合，詳細算法如下所示。

算法1構建開發者-項目二分網絡算法

4.2 創建投影圖

創建投影圖對識別內部邊和內部邊排序至關重要，在開發者-項目二分網絡中，如果兩個開發者共同參與過一個項目，那么他們之間就連邊，通過這種向下投影的方法可以將開發者-項目二分網絡轉換成開發者-開發者網絡（投影圖），詳細算法如下所示。

算法2下投影算法

由于二部圖投影會造成部分信息的丟失，在構建投影圖的過程中，通過給導出邊賦予相應的權重可以保留這類信息。在投影圖中，兩個節點之間邊的權重代表這兩個節點之間的局部相似性。在鏈路預測中，所有局部相似性度量方法都基于兩個節點的鄰居。本文使用三種指標給導出邊賦予權重，如表1所示。Common Neighbors指標表示二部圖中底部兩個節點共同鄰居的數量，即兩個開發者共同參與的項目數；Jaccard指標和Common Neighbors指標類似，不僅考慮了兩個節點共同鄰居的數量，還考慮到了兩個節點各自的鄰居數目，即兩個開發者共同和各自參與的項目數；Delta指標考慮到了兩個節點鄰居數量不均衡的情況，即一個開發者參與了很多項目，而另一個開發者卻只參與了很少的項目。利用權重函數對二部圖進行加權投影，可以得到相應的加權投影圖GD-PROJ。

表1 局部相似性度量

4.3 識別內部邊

內部邊本質上是當前二部圖中不存在的邊的子集，首先在開發者-項目二分網絡中增加一條邊，然后尋找出這條邊所有的導出邊，如果所有的導出邊在該二分網絡的投影圖中已經存在，那么這條邊就是內部邊，并把這條邊添加到內部邊的集合，詳細算法如下所示。

算法3識別內部邊算法

4.4 內部邊排序

本文通過預測內部邊對開發者進行項目推薦。本文方法的基本思想是如果兩個節點在當前二部圖中存在共同鄰居，那么它們將來也很有可能會有共同鄰居（如果兩個開發者共同參與開發過某個項目，那么他們將來很可能會合作參與開發另外的項目）；更進一步講，如果兩個節點在當前二部圖中有很多共同鄰居，那么它們將來可能會有更多共同鄰居（如果兩個開發者共同參與開發過很多項目，那么他們將來更有可能合作參與開發更多的項目），內部邊恰恰滿足這兩個標準。當識別內部邊以后，可以利用內部邊的導出邊在對應的加權投影圖中節點之間的權重的和對內部邊進行排序，詳細算法如下所示。

算法4內部邊排序算法

5 實驗

5.1 實驗數據

采用內部邊的方法對開發者進行項目推薦需要一個動態的大規模二分數據集，使用GNOME數據集作為實驗對象，提取開發者以及開發者參與過開發的項目信息，并在這些信息基礎上預測開發者還會參與哪些新項目。對于本文方法，參考期和預測期的選擇至關重要。GNOME項目持續時間從1997年到2013年，按時間順序對數據集進行了平均分割，2005年以前為參考期，2005年以后為預測期。對于二部圖G=（Developers，Items，Joins）參考期的基本特征和預測期新增邊的情況，如表2所示。

表2 GNOME數據集二部圖的基本信息

5.2 評價標準

本文在2005年以及之前數據基礎上預測邊P，此時，數據集中已有的邊為E，2005年以后數據集中真正新出現的邊為E′。本文方法僅考慮二部圖中邊的增加產生的變化，不考慮邊的減少以及節點的增加或減少產生的變化，詳細的評價框架如圖2所示，其中Pˉ=(D×U-E-P)表示當前二部圖的未知邊中沒有被預測出的邊集合。從圖2可以看到，未知邊被分為了四類：集合P?E′代表真陽性，即在預測期真正出現，本文方法在參考期也預測出來的邊；集合P-E′為假陽性，即在預測期沒有出現，但本方法在參考期卻預測出來的邊；集合Pˉ?E′為假陰性，即在預測期真正出現，但本方法在參考期沒有預測出來的邊；集合Pˉ-E′為真陰性，即在預測期沒有出現，本文方法在參考期也沒有預測出來的邊。本文方法的最終目標就是在最大化真陽性和真陰性的同時最小化假陽性和假陰性。這里使用AUC（Area Under the ROC Curve）對本文所采用的方法進行評價，并與協同過濾方法進行了比較。ROC（Receiver Operating Characteristic）曲線描繪了真陽性率對假陽性率的比率，AUC越大，真陽性率對假陽性率的比率就越高，預測的效果就越好。另外，本文使用準確率和召回率檢驗預測邊的數量對預測方法的影響。

圖2 評價框架

5.3 實驗結果及分析

5.3.1 預測邊數量的影響

為了評價所提方法的有效性，首先驗證了預測邊的數量||

P對本文方法和協同過濾方法的影響。計算預測邊數量||

P在所有取值情況下兩種方法的準確率和召回率，圖3顯示了在Jaccard指標下，內部邊方法和協同過濾方法的準確率和召回率隨預測邊數量的變化情況。在所有的權重指標下，預測邊的數量都隨著權重閾值的增加而減少。當閾值為0時，所有的內部邊都會被預測，對應的GNOME數據集中有15.67%的邊將會出現。雖然此時預測出來的邊包含了所有的內部邊，但很多沒有實際出現的邊同時也被預測出來，所以對應的準確率為0。相反的，當閾值設置非常高時，那么較少的內部邊被預測出來，因此對應的召回率幾乎為0，但對應的準確率卻達到100%。一般來說，預測邊的數量對預測方法的性能有很大的影響。圖3顯示隨著預測邊數量的增加，準確率下降，召回率上升。通常，需要在這兩個性能指標中進行折中考慮。從圖3也可以看出，內部邊方法明顯好于協同過濾方法。

圖3 預測邊數量對預測方法的影響

5.3.2 權重函數的影響

為了分析權重函數對預測方法的影響，本文設置了三組對比實驗，分別驗證了三種不同的權重指標對預測效果的影響，實驗結果如表3所示。

表3 不同權重指標下的AUC

實驗結果可以得出，三種權重指標中Delta指標的效果最好，另外采用Jaccard指標和Delta指標的內部邊方法相比于協同過濾方法AUC更大，Common Neighbors指標和協同過濾的方法相當，說明基于內部邊的項目推薦方法有比較準確的預測效果。

6 總結與下一步的工作

本文提出了一種基于內部邊的方法對開發者進行項目推薦，并在GNOME數據集上進行了驗證，實驗結果表明該方法取得了比協同過濾更好的預測效果。本文方法的主要優勢在于完全利用網絡結構和網絡分析技術對開發者進行項目推薦。在今后的研究工作中，將從以下幾方面進行完善：（1）利用更多不同規模的軟件生態系統對基于內部邊的推薦方法進行有效性驗證；（2）考慮更多權重函數和新的加權投影方法提高預測的效果；（3）優化算法，提高算法的效率。

[1]Robillard M，Walker R.Recommendation systems for software engineering[J].Software，2010，27（4）：80-86.

[2]Mockus A，Herbsleb J D.Expertise browser：A quantitative approach to identifying expertise[C]//Proceedings of the 24th International Conference on Software Engineering，2002：503-512.

[3]Goeminne M，Mens T.Analysing ecosystems for open source software developer communities[M]//Software Ecosystems：Analyzing and Managing Business Networks in the Software Industry.[S.l.]：Edward Elgar，2013.

[4]Goeminne M，Claes M，Mens T.A historical dataset for the GNOME ecosystem[C]//Proceedings of the 10th Working Conference on Mining Software Repositories，2013：225-228.

[5]Thung F，Bissyandé T F，Lo D，et al.Network structure of social coding in github[C]//Proceedings of 17th European Conference on Software Maintenance and Reengineering，2013：323-326.

[6]Surian D，Lo D，Lim E P.Mining collaboration patterns from a large developer network[C]//Proceedings of 17th Working Conference on Reverse Engineering，2010：269-273.

[7]Lima A，Rossi L，Musolesi M.Coding together at scale：Github as a collaborative social network[C]//Proceedings of the 8th AAAI International Conference on Weblogs and Social Media，2014.

[8]Zimmermann T，Zeller A，Weissgerber P，et al.Mining version histories to guide software changes[J].IEEE Transactions on Software Engineering，2005，31（6）：429-445.

[9]Mockus A，Herbsleb J.Expertise browser：A quantitative approach to identifying expertise[C]//Proceedings of the 24th International Conference on Software Engineering，2002：503-512.

[10]McDonald D W，Ackerman M S.Expertise recommender：A flexible recommendation system and architecture[C]//Proceedings of the 7th ACM Conference on Computer Supported Cooperative Work，2000：231-240.

[11]Surian D，Liu N，Lo D，et al.Recommending people in developers’collaboration network[C]//Proceedings of 18th Working Conference on Reverse Engineering，2011：379-388.

[12]楊習輝，李兵.一種群體軟件開發中的項目推薦方法[J].小型微型計算機系統，2015，36（4）：671-676.

[13]何鵬，李兵.Roster：一種開發者潛在同行推薦方法[J].計算機學報，2014（4）：859-872.

[14]Liben-Nowell D，Kleinberg J.The link prediction problem for social networks[C]//Proceedings of the 12th International Conference on Information and Knowledge Management，2003：370-381.

[15]Hasan M A，Chaoji V，Salem S，et al.Link prediction using supervised learning[C]//Proceedings of SDM workshop on Link Analysis，2006：798-805.

[16]O’Madadhain J，Hutchins J，Smyth P.Prediction and ranking algorithms for event-based network data[C]//Proceedings of 2005 Conference on Knowledge Discovery and Data Mining，2005：23-30.

[17]Huang Z，Li X，Chen H.Link prediction approach to collaborative filtering[C]//Proceedings of the Joint Conference on Digital Libraries，2005：141-142.

[18]Benchettara N，Kanawati R，Rouveirol C.Supervised machine learning applied to link prediction in bipartite social networks[C]//Proceedings of International Conference on Advances in Social Network Analysis and Mining，2010：158-168.

[19]Xie F，Chen Z，Shang J，et al.A link prediction approach for item recommendation with complex number[J].Knowledge-Based Systems，2015，81（6）：148-158.

[20]Sherkat E，Rahgozar M，Asadpour M.Structural link prediction based on ant colony approach in social networks[J].Statistical Mechanics and its Applications：Physica A，2015，419（8）：80-94.

[21]Allali O，Magnien C，Latapy M.Internal link prediction：a new approach for predicting links in bipartite graphs[J].Social Network Analysis and Mining，2013，3（1）：85-91.