計(jì)算機(jī)設(shè)計(jì)大賽炫酷展示

1、背景與意義背景與意義功能介紹功能介紹技術(shù)知識技術(shù)知識創(chuàng)新之處創(chuàng)新之處1234未來展望未來展望5 社會網(wǎng)絡(luò)（social network）是由圖表示的異構(gòu)多關(guān)系數(shù)據(jù)集，圖中節(jié)點(diǎn)對應(yīng)對象，邊對應(yīng)表示對象間聯(lián)系或相互作用的鏈接。過去的幾十年間，社會網(wǎng)絡(luò)受到越來越多的關(guān)注。特別是移動網(wǎng)絡(luò)和互聯(lián)網(wǎng)的發(fā)展，產(chǎn)生了大量的，容易被計(jì)算機(jī)處理的社會網(wǎng)絡(luò)數(shù)據(jù)。從這些數(shù)據(jù)中獲取知識，從而理解商業(yè)行為，識別業(yè)務(wù)模式，捕捉用戶行為，更好利用資源，提高服務(wù)質(zhì)量，將成為運(yùn)營商的核心競爭力之一。 對于現(xiàn)在大數(shù)據(jù)的時代中，挖掘出社交網(wǎng)絡(luò)上的社區(qū)很有實(shí)用價值。社區(qū)內(nèi)用戶的共同話題，會形成一個定向的區(qū)別用戶的方式，為智能搜索、個性

2、化服務(wù)、商業(yè)應(yīng)用推廣等應(yīng)用提供理論依據(jù)。從廣告投放的角度來看，容易找到定向的廣告受眾; 從朋友推薦的角度看，能夠方便的將同一個社區(qū)內(nèi)的個體向其他個體進(jìn)行推薦，為找尋多年沒有聯(lián)系的朋友提供一個方便快捷的途徑。 將社會網(wǎng)絡(luò)分析以一種數(shù)據(jù)可視化的形式展示給決策者，不僅能形象直觀，還有助于其在龐大的數(shù)據(jù)中能及時捕獲所需信息。數(shù)據(jù)可視化，是關(guān)于數(shù)據(jù)之視覺表現(xiàn)形式的研究。如今，可視化已經(jīng)不僅僅是點(diǎn)和線的簡單描繪，它成為了一種能傳遞深層數(shù)據(jù)內(nèi)涵、啟發(fā)問題解決方案的強(qiáng)大智能模型。 類似這樣的軟件，在國外著名的有UCINET、Pajek以及Gephi等，UCINET、Pajek側(cè)重于社會網(wǎng)絡(luò)的分析，但可視化的效

3、果較差，而且操作不簡單，忽略用戶體驗(yàn)；Gephi是則偏向于社交圖譜的數(shù)據(jù)可視化，能生成漂亮的可視化圖形，并對數(shù)據(jù)進(jìn)行清洗和分類，但數(shù)據(jù)分析不夠全面，提供算法較少。另外，這些軟件都需用戶下載才能使用，不支持web端，這樣導(dǎo)致電腦因系統(tǒng)的差異而使用不了某些軟件，如Gephi需jdk1.7以下的環(huán)境配置，不支持jdk1.8。 針對上述的不足，我們小組研發(fā)了一個基于web端的社會網(wǎng)絡(luò)可視化分析平臺，名為vina，力求將社會網(wǎng)絡(luò)分析與數(shù)據(jù)可視化充分結(jié)合，以給用戶更好的體驗(yàn)效果。 項(xiàng)目簡介： 本系統(tǒng)是一個基于開源框架Django的社會網(wǎng)絡(luò)可視化分析網(wǎng)站，并且盡可能簡單靈活地使數(shù)據(jù)可視化。特點(diǎn)是UI美觀、使

4、用簡單、支持大多數(shù)瀏覽器、支持多種文件格式的輸入、提供多種社區(qū)劃分算法。數(shù)據(jù)可視化的結(jié)果包括了網(wǎng)絡(luò)圖、柱狀圖、餅圖、表格，讓用戶從不同角度獲得社區(qū)網(wǎng)絡(luò)劃分的結(jié)果。另外，本系統(tǒng)還運(yùn)用了社會網(wǎng)絡(luò)分析的知識，為用戶挖掘出網(wǎng)絡(luò)中的重要信息。本系統(tǒng)的用途可分為：客戶群體細(xì)分、社交網(wǎng)絡(luò)分析、熱點(diǎn)事件分析、輿情監(jiān)控、社會網(wǎng)絡(luò)劃分的教學(xué)等。 支持多種文件格式的輸入提供多種社區(qū)劃分算法UI美觀使用簡單基于web項(xiàng)目特點(diǎn)： 項(xiàng)目用途： 登陸網(wǎng)站，登陸網(wǎng)站，注冊登錄注冊登錄 導(dǎo)入文件，導(dǎo)入文件，選擇算法選擇算法 得到輸出，得到輸出，分析結(jié)果分析結(jié)果退出登錄退出登錄系統(tǒng)使用流程：本系統(tǒng)的網(wǎng)址為http：/120.25

5、.203.152:8000文件導(dǎo)入格式： 我們導(dǎo)入的文件有兩個，第一個是網(wǎng)絡(luò)信息文件，文件的內(nèi)容以source，target，weight為格式，source代表源點(diǎn)，target代表目標(biāo)點(diǎn)，weight代表連邊權(quán)重，例如節(jié)點(diǎn)1對節(jié)點(diǎn)6有連邊，連邊權(quán)重為2，我們記錄的格式為“1,6,2”。 第二個是節(jié)點(diǎn)標(biāo)簽文件，文件的內(nèi)容是節(jié)點(diǎn)所對應(yīng)的標(biāo)簽，以node，label為格式，例如節(jié)點(diǎn)1的標(biāo)簽叫quincy。 兩份文件均支持txt，xls和csv格式 網(wǎng)絡(luò)信息文件：網(wǎng)絡(luò)信息文件：標(biāo)簽文件標(biāo)簽文件LPABGLL WALK-TRAPFAST-GREEDY WorldCannotReceiveWorldC

6、annotSeeWorld doesNot KnowWillDwell inDisciples社區(qū)劃分算法社區(qū)劃分算法四種算法都具有良好的社區(qū)劃分效果，四種算法都具有良好的社區(qū)劃分效果，不同的算法適用于不同的場景不同的算法適用于不同的場景LPA：快速高效：快速高效 BGLL：穩(wěn)定準(zhǔn)確穩(wěn)定準(zhǔn)確 Walktrap：劃分效果好：劃分效果好 Fastgreedy： 適用大型加適用大型加權(quán)網(wǎng)絡(luò)權(quán)網(wǎng)絡(luò) 算法特點(diǎn)：算法特點(diǎn)：1、label propagation Algorithm(LPA) 標(biāo)簽傳播算法（標(biāo)簽傳播算法（LPALPA）是由）是由ZhuZhu等人于等人于20022002年提出，它是一種基于圖的

7、半年提出，它是一種基于圖的半監(jiān)督學(xué)習(xí)方法該算法的基本原理如下：首先，給全網(wǎng)每個節(jié)點(diǎn)分配一個不重監(jiān)督學(xué)習(xí)方法該算法的基本原理如下：首先，給全網(wǎng)每個節(jié)點(diǎn)分配一個不重復(fù)的標(biāo)簽（復(fù)的標(biāo)簽（labellabel）；其次，在迭代的每一步，讓一個節(jié)點(diǎn)采用在它所有的）；其次，在迭代的每一步，讓一個節(jié)點(diǎn)采用在它所有的鄰居節(jié)點(diǎn)中最流行的標(biāo)簽（如果最佳候選標(biāo)簽超過一個，則在其中隨機(jī)抽一鄰居節(jié)點(diǎn)中最流行的標(biāo)簽（如果最佳候選標(biāo)簽超過一個，則在其中隨機(jī)抽一個），；最后，在迭代收斂時，采用同一種標(biāo)簽的節(jié)點(diǎn)被歸入同一個社區(qū)。個），；最后，在迭代收斂時，采用同一種標(biāo)簽的節(jié)點(diǎn)被歸入同一個社區(qū)。 這個算法的核心是通過標(biāo)簽的擴(kuò)散來模

8、擬某種流在網(wǎng)絡(luò)上的擴(kuò)散。其優(yōu)勢是這個算法的核心是通過標(biāo)簽的擴(kuò)散來模擬某種流在網(wǎng)絡(luò)上的擴(kuò)散。其優(yōu)勢是算法簡單，特別適用于分析被流所塑造的網(wǎng)絡(luò)。在大多數(shù)情況下可以快速收算法簡單，特別適用于分析被流所塑造的網(wǎng)絡(luò)。在大多數(shù)情況下可以快速收斂。其缺陷是，迭代的結(jié)果有可能不穩(wěn)定，尤其在不考慮連邊的權(quán)重時，如斂。其缺陷是，迭代的結(jié)果有可能不穩(wěn)定，尤其在不考慮連邊的權(quán)重時，如果社區(qū)結(jié)構(gòu)不明顯，或者網(wǎng)絡(luò)比較小時，有可能所有的節(jié)點(diǎn)都被歸入同一個果社區(qū)結(jié)構(gòu)不明顯，或者網(wǎng)絡(luò)比較小時，有可能所有的節(jié)點(diǎn)都被歸入同一個社區(qū)。社區(qū)。 Reference:Raghavan, U.N. and Albert, R. and Ku

9、mara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E76:036106, 2007. /abs/0709.2938 .技術(shù)知識技術(shù)知識2、BGLL 這個方法分兩步：這個方法分兩步：（1 1）從節(jié)點(diǎn)合并開始，）從節(jié)點(diǎn)合并開始， 構(gòu)建第一步社團(tuán)劃分結(jié)果。每個節(jié)點(diǎn)根據(jù)模塊度增構(gòu)建第一步社團(tuán)劃分結(jié)果。每個節(jié)點(diǎn)根據(jù)模塊度增益決定是否加入到鄰居節(jié)點(diǎn)的社團(tuán)中和到底加入到哪個鄰居節(jié)點(diǎn)的社團(tuán)中。益決定是否加入到鄰居節(jié)點(diǎn)的社團(tuán)中和到底

10、加入到哪個鄰居節(jié)點(diǎn)的社團(tuán)中。每個節(jié)點(diǎn)按序執(zhí)行該過程。每個節(jié)點(diǎn)按序執(zhí)行該過程。（2 2）重新構(gòu)建網(wǎng)絡(luò)。把第一步每個社團(tuán)單做一個節(jié)點(diǎn)，邊是原來社團(tuán)之間）重新構(gòu)建網(wǎng)絡(luò)。把第一步每個社團(tuán)單做一個節(jié)點(diǎn)，邊是原來社團(tuán)之間鏈接邊權(quán)的和。鏈接邊權(quán)的和。（3 3）迭代（迭代（1 1），（），（2 2），直到收斂。），直到收斂。 Reference: VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks. J Stat Mech P10008(

11、2008), /abs/0803.04763、Walktrap 算法的初始條件為每個結(jié)點(diǎn)為一個單獨(dú)的社區(qū)，然后逐步合并可使結(jié)點(diǎn)和算法的初始條件為每個結(jié)點(diǎn)為一個單獨(dú)的社區(qū)，然后逐步合并可使結(jié)點(diǎn)和它所在社區(qū)之間的平方距離均值達(dá)到最小的兩個社區(qū)。每一步都要更新社區(qū)它所在社區(qū)之間的平方距離均值達(dá)到最小的兩個社區(qū)。每一步都要更新社區(qū)之間的距離，其中兩個結(jié)點(diǎn)之間的距離對應(yīng)于它們的相似度，即在一個離散之間的距離，其中兩個結(jié)點(diǎn)之間的距離對應(yīng)于它們的相似度，即在一個離散的隨機(jī)游走過程中，它們之間的方向轉(zhuǎn)移概率。的隨機(jī)游走過程中，它們之間的方向轉(zhuǎn)移概率。 Reference: Pas

12、cal Pons, Matthieu Latapy: Computing communities in large networks using random walks, /abs/physics/0512106 4、Fastgreedy 一種基于貪婪法思想的凝聚算法，并稱這種算法為快速算法。將網(wǎng)絡(luò)劃分一種基于貪婪法思想的凝聚算法，并稱這種算法為快速算法。將網(wǎng)絡(luò)劃分為為K K個社團(tuán)，定義一個個社團(tuán)，定義一個k k* *k k維的對稱矩陣維的對稱矩陣E=E=（），其中元素，表示網(wǎng)絡(luò)連接兩（），其中元素，表示網(wǎng)絡(luò)連接兩個不同社團(tuán)的節(jié)點(diǎn)的邊在所有邊中占的比例；這兩個節(jié)

13、點(diǎn)分別位于第個不同社團(tuán)的節(jié)點(diǎn)的邊在所有邊中占的比例；這兩個節(jié)點(diǎn)分別位于第i i個社個社區(qū)和第區(qū)和第j j個社區(qū)。個社區(qū)。1.1.初始化網(wǎng)絡(luò)為初始化網(wǎng)絡(luò)為N N個社團(tuán)，即每個節(jié)點(diǎn)就是一個獨(dú)立社團(tuán)。個社團(tuán)，即每個節(jié)點(diǎn)就是一個獨(dú)立社團(tuán)。2.2.依次合并有邊相連的社團(tuán)對，并計(jì)算合并后的模塊度增量，根據(jù)貪婪算法依次合并有邊相連的社團(tuán)對，并計(jì)算合并后的模塊度增量，根據(jù)貪婪算法的原理，每次合并應(yīng)該沿著模塊度增大最多或者減少最少的方向進(jìn)行。每次的原理，每次合并應(yīng)該沿著模塊度增大最多或者減少最少的方向進(jìn)行。每次合并以后，對對應(yīng)的元素更新，并將與合并以后，對對應(yīng)的元素更新，并將與i i、j j社團(tuán)相關(guān)的行和列相加

14、。社團(tuán)相關(guān)的行和列相加。3.3.重復(fù)步驟重復(fù)步驟2 2，不斷合并社團(tuán)，直到整個網(wǎng)絡(luò)都合并為一個社團(tuán)。，不斷合并社團(tuán)，直到整個網(wǎng)絡(luò)都合并為一個社團(tuán)。4.4.整個算法完成后，得到一個社區(qū)結(jié)構(gòu)分解的樹狀圖。再通過選擇在不同位整個算法完成后，得到一個社區(qū)結(jié)構(gòu)分解的樹狀圖。再通過選擇在不同位置斷開可以得到不同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。在這些社區(qū)結(jié)構(gòu)中，選擇一個對應(yīng)局置斷開可以得到不同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。在這些社區(qū)結(jié)構(gòu)中，選擇一個對應(yīng)局部最大模塊度值的結(jié)構(gòu)，就得到最好的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。部最大模塊度值的結(jié)構(gòu)，就得到最好的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。 Reference: A. Clauset, M. E. J. Newman and C

15、. Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004).社區(qū)劃分 通過社區(qū)劃分算法將一個網(wǎng)絡(luò)劃分成不同社區(qū)，同一個社區(qū)的節(jié)點(diǎn)聯(lián)系較為緊密，不同社區(qū)的節(jié)點(diǎn)聯(lián)系較為稀疏。效果如下： 社會網(wǎng)絡(luò)分析社區(qū)結(jié)構(gòu)分析核心人物挖掘好友推薦核心人物挖掘：中心性分析： 描述圖中任何一點(diǎn)在網(wǎng)絡(luò)中占據(jù)的核心性源于社會計(jì)量學(xué)的”明星“概念，一個核心點(diǎn)是那種處于一系列關(guān)系核心的位置，即該點(diǎn)與其他點(diǎn)有眾多的直接聯(lián)系。若某點(diǎn)具有最高點(diǎn)度中心度，則稱該點(diǎn)居于中心。 我們通過點(diǎn)度中心度挖掘出網(wǎng)絡(luò)中核心人物，

16、而點(diǎn)度中心度可分為絕度中心度和相對中心度。一般采用相對中心度較為準(zhǔn)確。社區(qū)結(jié)構(gòu)分析：社區(qū)結(jié)構(gòu)分析：1.1.社區(qū)密度：社區(qū)密度： 反映社區(qū)內(nèi)的緊密程度，密度值反映社區(qū)內(nèi)的緊密程度，密度值0 0到到1 1之間，越接近之間，越接近1 1則代表彼此關(guān)系越則代表彼此關(guān)系越緊密。緊密。 一般將密度定義為一般將密度定義為“圖中實(shí)際存在的線的條數(shù)圖中實(shí)際存在的線的條數(shù)/ /圖中理論上最多可能產(chǎn)圖中理論上最多可能產(chǎn)生的生的 線的條數(shù)線的條數(shù)”。當(dāng)圖中點(diǎn)的個數(shù)為。當(dāng)圖中點(diǎn)的個數(shù)為n n時，密度可以表示為時，密度可以表示為l/n(n-l/n(n-1)/2.1)/2. 其中分子其中分子l l是圖中實(shí)際存在的線的條數(shù)，

17、是所有點(diǎn)度數(shù)總和的一半，也是圖中實(shí)際存在的線的條數(shù)，是所有點(diǎn)度數(shù)總和的一半，也就是就是 鄰接陣中所有元素總和的一半。而分母可以用簡單的排列組合方鄰接陣中所有元素總和的一半。而分母可以用簡單的排列組合方法計(jì)算得到。法計(jì)算得到。2.2.點(diǎn)度中心勢點(diǎn)度中心勢 反映社區(qū)內(nèi)的集中程度，也間接反映核心人物對社區(qū)的影響程度。反映社區(qū)內(nèi)的集中程度，也間接反映核心人物對社區(qū)的影響程度。 思路：思路： 首先找到圖中的最大中心度數(shù)值；然后計(jì)算該值與任何其他點(diǎn)的中心度的差，首先找到圖中的最大中心度數(shù)值；然后計(jì)算該值與任何其他點(diǎn)的中心度的差， 從而得出多個從而得出多個“差值差值”；再計(jì)算這些；再計(jì)算這些“差值差值”的總和；最后用這個總和除的總和；最后用這個總和除以各個以各個“差值差值”總和的最大可能值?？偤偷淖畲罂赡苤?。 公式：公式：好友推薦：把好友關(guān)系轉(zhuǎn)化成圖的形式，點(diǎn)代表一個用戶，連接兩點(diǎn)的邊代表兩個用戶是好友，邊可以有權(quán)重，也可以沒有。直接認(rèn)識的朋友，叫一度好友。朋友的朋友，叫二度好友，而我們主要通過二度好友進(jìn)行好友推薦，即“朋友的朋友”的思想。 1