基于超圖的在線社會網(wǎng)絡(luò)模型

基于超圖的在線社會網(wǎng)絡(luò)模型

0算法1:平臺上的二元和內(nèi)容在線社交網(wǎng)絡(luò)是幫助用戶建立在線朋友之間的關(guān)系的一個話題，并允許用戶可以在朋友之間建立自己的興趣和活動。在線社會網(wǎng)絡(luò)中最重要的兩個角色是內(nèi)容（如視頻、圖像、論壇等），其中之一是用戶。內(nèi)容、回帖和瀏覽等活動,面對這些實時產(chǎn)生的海量內(nèi)容,分析用戶行為并且快速定位基于共同興趣的用戶,有利于預(yù)測熱點話題,監(jiān)控突發(fā)性網(wǎng)絡(luò)群體事件等。目前,用戶和內(nèi)容之間的映射關(guān)系采用二部圖的方法來描述,分別用一組點表示用戶,另一組點表示內(nèi)容,這樣一來,在同一張圖中就出現(xiàn)了兩類不同質(zhì)的點,對于很多拓?fù)湫再|(zhì)的研究產(chǎn)生了障礙,也有一些方法將二分圖投影為單模式來處理,但是實際用戶的隱性關(guān)系沒法直觀地表現(xiàn)出來。為了更好地解決這些問題,同時又不破壞同一網(wǎng)絡(luò)中點定義的同質(zhì)性,采用超圖來描述。內(nèi)容都是由用戶通過某種行為活動而產(chǎn)生,如發(fā)布分享新內(nèi)容。1互聯(lián)網(wǎng)社會網(wǎng)絡(luò)的特點定義1給定圖G=(V,E)如果頂點集V可分為兩個互不相交的非空子集X和Y,并且圖中的每條邊(i,j)的兩個端點i和j分別屬于這兩個不同的頂點子集,那么就稱圖G為一個二分圖,記為G=(X,E,Y)。在線社會網(wǎng)絡(luò)中,包括BBS和各種論壇等常常具有一種討論線的結(jié)構(gòu),例如,某個用戶發(fā)一個關(guān)于某個話題的帖子,然后一些其他用戶回帖來參與討論或回答問題?？梢园凑杖缦路绞疆a(chǎn)生一個二分網(wǎng)絡(luò):集合X中的每個節(jié)點代表一個用戶,集合Y中的每個節(jié)點代表一類話題內(nèi)容。如果某個用戶發(fā)了關(guān)于某個話題的第一個帖子或者就某個話題回帖,那么就在該用戶與該話題之間有一條邊。目前在分析社會網(wǎng)絡(luò)時,把二分圖投影為單模式圖,即投影到由集合X中頂點構(gòu)成的單分圖:如果在原來的二分圖中,集合X中兩個頂點都與集合Y中的某個頂點相連,那么在對應(yīng)的單分圖中,這兩個頂點之間就有一條邊,同樣,也可以把該二分圖投影到由集合Y中頂點構(gòu)成的單分圖,然后再分析所得到的單分圖的拓?fù)湫再|(zhì)。一般情況下網(wǎng)絡(luò)社團(tuán)中用戶上網(wǎng)只會瀏覽部分版塊中的部分內(nèi)容,所以鎖定用戶操作的版塊更能快速定位用戶的興趣愛好內(nèi)容。假設(shè)5個用戶參與了5個版塊:V={v1,v2,v3,v4,v5},D={d1,d2,d3,d4,d5},同時假設(shè)不存在重邊,即用戶在同一個版塊中的多種行為視為一次行為則用戶與版塊之間連接一條邊。如圖1所示,圖中上半部分是描述在線社會網(wǎng)絡(luò)的雙粒子圖,其中圓圈頂點表示用戶,正方形頂點表示版塊,下半部分表示基于共同版塊的用戶連邊。在二分圖中,只能觀察到某個用戶擁有的版塊規(guī)?；蛘吣硞€版塊擁有的用戶規(guī)模,而無法直觀地表征用戶節(jié)點之間的隱性關(guān)系和用戶的多種行為,并且面對在線網(wǎng)絡(luò)的海量數(shù)據(jù)時,利用二部圖表征用戶特征會形成復(fù)雜的拓?fù)浣Y(jié)構(gòu),不利于數(shù)據(jù)特征的挖掘。顯然,該方法適合處理小規(guī)模的數(shù)據(jù)。因此,提出采用超圖的數(shù)學(xué)原理解決上述問題。2超圖的邊界條件超圖的理論基礎(chǔ)是圖論和集合。具有共同屬性特征的對象屬于一個集合,不同的抽象層次可歸屬于集合的集合;如此構(gòu)成以集合的包含關(guān)系為基礎(chǔ)的結(jié)構(gòu),這種結(jié)構(gòu)可用超圖來表示。定義2超圖設(shè)V={v1,v2,…,vn}是一個有限集,若:則稱二元關(guān)系H=(V,E)為一個超圖。V的元素v1,v2,v3,…,vn稱為超圖的頂點,E={e1,e2,…,en}是超圖的邊集合,集合ei={vi1,vi2,…,vij}(i=1,2,…,m)稱為超邊。定義3超圖H的對偶圖H*如果對所有的j,Vj={ei|i≤m,vj∈Ei},vj≠Ф,ue420j,∪jVj=E,那么超圖H*=(E;V1,V2,…,Vn)稱為H的對偶。顯然,(H*)*=H。前面提到的二部圖中有5個用戶,(v1,v2,v3,v4,v5)參與了5個版塊(d1,d2,d3,d4,d5),同樣假設(shè)用戶在同一個版塊中的多種行為視為一次行為。超圖的表示如下:如果某個版塊有多個用戶參與,此時就可以形成一個以用戶為頂點,版塊為超邊的超圖H=(V,D),如圖2所示。H=({v1,v2,v3,v4,v5},{d1,d2,d3,d4,d5})其中:通過集合直觀地反映出版塊用戶的規(guī)模,如版塊d1中用戶數(shù)為3個,分別是v1,v2,v5。另外,如果某個用戶參與多個版塊,就形成以版塊為頂點,用戶為超邊的圖3的對偶圖H*=(D,V)。其中:用戶感興趣的版塊就一目了然了。模擬圖中顯示用戶5操作3個版塊(d1,d4,d5),對其他版塊不會花費時間操作。顯然,超圖更容易表征海量數(shù)據(jù)中版塊和用戶的規(guī)模。3內(nèi)容為點對點的超圖為了詳盡地刻畫并分析實體、用戶行為、版塊、內(nèi)容四者之間的映射關(guān)系以及基于用戶興趣度的潛在朋友關(guān)系,本文建立基于超圖集合理論的在線社會網(wǎng)絡(luò)的四層超模型:實體、用戶行為、興趣內(nèi)容及版塊。模型中假設(shè)網(wǎng)絡(luò)不存在自環(huán),即忽略用戶回復(fù)自己帖子時形成的自環(huán),不考慮由于用戶之間存在多次的回復(fù)關(guān)系形成的多次行為。假設(shè):以內(nèi)容為頂點,用戶為超邊的超圖H=(C,V),C=(c1,c2,c3,c4,c5,c6,c7,c8,c9,c10)。H(C,V)=({c1,c2,c3,c4,c5,c6,c7,c8,c9,c10},{v1,v2,v3,v4,v5})其中,v1(c1),v2(c1,c2,c3),v3(c2,c3,c8),v4(c5,c6),v5(c1,c8,c9,c10)用戶v5關(guān)注的內(nèi)容最多,用戶v2,v3共同關(guān)注內(nèi)容c2和c3。假設(shè):d1(c1),d2(c2,c3,c4),d3(c5,c6,c7),d4(c8,c9),d5(c10)其中版塊d2有三個內(nèi)容c2,c3,c4。如圖4所示的超網(wǎng)絡(luò)結(jié)構(gòu)。圖4中用戶v2和v3的操作行為:用戶v2發(fā)布主題貼c2并回復(fù)主題貼c3,用戶v3發(fā)布主題貼c3并回復(fù)主題貼c2,表明c2,c3是他們共同的興趣內(nèi)容。下面根據(jù)超圖理論關(guān)系映射出四層超網(wǎng)絡(luò)型。(1)潛在朋友關(guān)系實體:在線網(wǎng)絡(luò)用戶通過實名注冊獲得一個ID序列,擁有這個ID序列的用戶就是網(wǎng)絡(luò)上的實體,他可以進(jìn)行各種網(wǎng)絡(luò)活動。從而和其他實體建立關(guān)系。實體關(guān)系有直接定義的好友關(guān)系,即用戶熟悉的人如同事、同學(xué)等彼此加為好友;潛在朋友關(guān)系,即通過共同感興趣的話題內(nèi)容映射而來,共同興趣內(nèi)容超過一定數(shù)量時用戶之間存在潛在朋友關(guān)系,但是面對在線網(wǎng)絡(luò)的海量數(shù)據(jù),個體用戶共同感興趣的內(nèi)容不易挖掘,因此,采用個體用戶對某個版塊的興趣程度來擬合共同興趣內(nèi)容。實體行為:實體在網(wǎng)絡(luò)中的各種活動,一般有發(fā)布新內(nèi)容,回帖,瀏覽,分享,收藏,微薄中添加關(guān)注粉絲等行為,設(shè)有n種行為,則根據(jù)第2節(jié)超圖理論得出實體行為關(guān)系矩陣如下:其中,行之和為某個用戶擁有的行為數(shù)。(2)行為分類及行為軌跡興趣:定義內(nèi)容為興趣元。行為興趣:用戶通過各種行為活動表征興趣愛好,矩陣關(guān)系如下:其中,行表示n種行為;列表示C個內(nèi)容。根據(jù)超圖定義列之和表示某個內(nèi)容的用戶行為。(3)基于超圖理論的學(xué)習(xí)體驗分析論壇中所有內(nèi)容被聚類到D個版塊中,目前在線網(wǎng)絡(luò)的版塊結(jié)構(gòu)是靜態(tài)的,由系統(tǒng)設(shè)計人員根據(jù)不同的內(nèi)容領(lǐng)域事先手動劃分而來的,矩陣關(guān)系如下:其中,列之和表征某個版塊中的內(nèi)容數(shù)。(4)實體興趣關(guān)系基于個體行為和興趣的差異性,通過超網(wǎng)絡(luò)映射實體關(guān)于興趣的差異性矩陣如下:即:從而得出實體版塊關(guān)系矩陣如下:其中,行表示實體用戶;列表示D個版塊。rm,d反映用戶對某個版塊的興趣程度。本文利用Pearson相關(guān)性指數(shù)得出實體間潛在的朋友關(guān)系:其中,表示用戶u的所有內(nèi)容的興趣平均值,Pearson相關(guān)性指數(shù)的絕對值越大,相關(guān)性越強(qiáng),相關(guān)系數(shù)越接近于1或-1,相關(guān)度越強(qiáng),相關(guān)系數(shù)越接近于0,相關(guān)度越弱。基于超圖理論,能很好地解釋用戶愛好形成的原因,即用戶有共同喜歡的話題。同時我們能快速定位用戶的興趣愛好,對版塊預(yù)測起到向?qū)ё饔谩?用戶使用體驗分析目前使用網(wǎng)絡(luò)新技術(shù)的中堅力量為80年代的人群,分析其網(wǎng)絡(luò)行為更能反映社會現(xiàn)象,本文選擇這類人群對其下一代的網(wǎng)絡(luò)教育作為研究對象,分析了某幼兒園論壇的用戶行為。該幼兒園實際規(guī)模比較大,具有一定的代表性。論壇擁有2157名注冊用戶,其中平均每日新增205個帖子、注冊會員數(shù)2人。論壇采用實名注冊,用戶的言論相對負(fù)責(zé),網(wǎng)絡(luò)行為能真實地反映用戶的興趣?；贘ava語言采集數(shù)據(jù),采集時間為2011年8月至2012年4月。采集到的數(shù)據(jù)統(tǒng)計如表1所示,為了得到直觀圖,只分析某班的論壇。該論壇開創(chuàng)時間短、用戶數(shù)較少,所以通過發(fā)布主題帖和回復(fù)兩種行為來表征用戶的興趣愛好,數(shù)據(jù)統(tǒng)計如表2所示。其中,論壇版塊為原創(chuàng)、討論、公告、求助、推薦、祝福、建議7個版塊。已存在實體好友關(guān)系是用戶直接在論壇內(nèi)互相加為好友。實體好友關(guān)系如圖5所示,為了保護(hù)隱私,采用姓名的首個大寫字母來表示實體。從圖中我們可以清楚地看到“hzlx”是一個樞紐節(jié)點,現(xiàn)實中該實體是本班的班主任。根據(jù)第3節(jié)定義的超圖映射理論,得出實體對應(yīng)行為、內(nèi)容聚類、實體對應(yīng)興趣的關(guān)系圖分別如下:(1)實體行為關(guān)系(2)內(nèi)容塊的關(guān)系其中原創(chuàng)比例最大,而“求助”版塊(圖7中的孤立節(jié)點)沒有家長關(guān)注,對論壇管理提供了更新或修改版塊的依據(jù)。(3)實體感染器其中實體“msx“操作的版塊有推薦、原創(chuàng)、建議3個版塊,而原創(chuàng)中有8個感興趣內(nèi)容。我們可以直觀地分析出用戶在不同版塊中興趣差異。(4)第二,有直接的朋友關(guān)系,但有-從矩陣中清楚地看到大部分節(jié)點之間的相似度在0.8~0.9之間,而實際中這些用戶部分為直接好友,部分雖然不是直接好友,但是他們之間互動較為頻繁,形成了一個隱性的關(guān)注圈。比如用戶“jj”在圖5中的實體好友關(guān)系中,沒有直接的好友關(guān)系,是一個孤立節(jié)點,但是在實體潛在朋友關(guān)系矩陣中,“jj”和大部分用戶有很高的興趣相似度?，F(xiàn)實中,“jj”熱衷于發(fā)主題帖和回復(fù)其他用戶的主題帖,表現(xiàn)出對這些話題的喜愛度,形成和其他用戶的潛在朋友關(guān)系。又如“fcj”和“tyf”具有直接好友關(guān)系,但是,他們沒有共同關(guān)注的話題,這種現(xiàn)象表明在線社會網(wǎng)絡(luò)中,雖為好友,但是其直接的交流反而更少。由于論壇的特殊性,本文將各個版塊中的所有興趣內(nèi)容自定義為6類愛好(即老師通知,家庭作業(yè),家長推薦,交流教育經(jīng)驗,日常生活,課堂活動),如表3所示。用戶對各種活動和家庭作業(yè)比較關(guān)注。5關(guān)注基礎(chǔ)上的4個群體本文以某幼兒園論壇為研究對象,采用超圖理論建立了實體用戶對應(yīng)興趣的超網(wǎng)絡(luò)模型,