信息科學(xué)與技術(shù)學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)專業(yè)技能大賽試題new

1、2012年信息科學(xué)與技術(shù)學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)專業(yè)技能大賽試題說(shuō)明：1、不限定開發(fā)語(yǔ)言 2、最多不超過(guò)5人/題 3、題目理解有問題找唐仕喜老師 4、比賽時(shí)間為1個(gè)月，到2013年1月1日前截止提交 5、10(2)(3)班所有學(xué)生都要參加比賽并提交作品，其它班級(jí)可參加 6、學(xué)院通過(guò)答辯評(píng)選擇出一、二、三等獎(jiǎng)若干名，并發(fā)放證書和獎(jiǎng)品【試題一】對(duì)給定文檔，依據(jù)下面的思想設(shè)計(jì)聚類算法，并實(shí)現(xiàn)，輸出聚類結(jié)果。無(wú)向加權(quán)圖G=V，E，W，V=d1，d2，dn；其表示形式為一對(duì)稱矩陣：wijn×n，其中W=w1，w2，wm是邊權(quán)重代表兩個(gè)文本間相似度。計(jì)算文檔的詞頻以及文檔間的相似度，將文檔粗化的聚成無(wú)

2、關(guān)或是相關(guān)度極小的c個(gè)文檔子類。首先除去在所有文檔中出現(xiàn)的高頻詞；然后提取剩下詞匯的短語(yǔ)存入詞根表中。收集這些短語(yǔ)形成一個(gè)索引短語(yǔ)集T。短語(yǔ)t在文檔di中權(quán)重為：tfij定義為短語(yǔ)t在文檔中di出現(xiàn)的頻率；dft定義為含有短語(yǔ)t的文檔數(shù)量；L定義為文檔di中包含的索引短語(yǔ)的數(shù)量；N定義為文檔的數(shù)量。p_term_documen（tt，di）的值代表著短語(yǔ)t在文檔di中的重要性，取值范圍是0，1。計(jì)算出短語(yǔ)的權(quán)重，可以將短語(yǔ)表示成向量：di=（wi1，wi2，wis），其中0wij1，s代表索引短語(yǔ)表中詞的數(shù)量。則兩個(gè)文檔di與dj的相似度可定義為： 由Wij=sim（di，dj），建立模糊相似

3、矩陣WRn×n，其中當(dāng)i=j時(shí)，令Wii=0。由相似矩陣求得傳遞閉包t(W)，選取一個(gè)合適的值得到一個(gè)截集，得到的將是一個(gè)0，1矩陣，記為t(R)。由此矩陣可以分成c個(gè)文檔類，即A=A1，A2，Ac，滿足了文檔類間的相似性極小，將c個(gè)文本集看成c個(gè)子圖。判斷各個(gè)文檔子類中如果存在只有一個(gè)文檔的類，將其并入其他與其相似度最高的子類中，變成c*個(gè)子圖。輸入c*個(gè)子圖，用基于譜圖分割簡(jiǎn)單的譜聚類算法對(duì)每個(gè)子圖G的頂點(diǎn)集Vk=（v1，v2，vn）進(jìn)行聚類，得到每個(gè)子圖的聚類結(jié)果及其對(duì)應(yīng)的類別數(shù)ki，其中i1，c*。計(jì)算出ki的和即為總的聚類數(shù)K。輸入一個(gè)數(shù)據(jù)集X=x1，x2，xk，輸出由以上

4、的數(shù)據(jù)集分割出來(lái)的k個(gè)子集。計(jì)算每個(gè)子圖的親密矩陣S，當(dāng)ij時(shí)，Sij=exp（-d（xi-x）j/22），Sii=0。構(gòu)造Laplacian矩陣L，L=D-1/2SD-1/2，其中D為對(duì)角陣。計(jì)算L的前k個(gè)特征值特征向量1，2，k（重復(fù)特征值取其互相正交的特征向量），按照大小順序?qū)⑾鄳?yīng)的特征向量排列構(gòu)成矩陣U=1，2，kRn×k，初始化聚類數(shù)m=2。令ki=m。取U的前ki個(gè)列向量構(gòu)成矩陣Y，即Y=U（：，1：k），歸一化Y為矩陣V，其中在ki維空間里，每個(gè)坐標(biāo)軸的正負(fù)方向分別標(biāo)記一個(gè)聚類。把V的行向量看作是ki維空間的點(diǎn)，將其標(biāo)記為距離最近的坐標(biāo)軸所標(biāo)記的聚類。這樣最多可以產(chǎn)生2

5、ki個(gè)聚類。除去空聚類和只有少數(shù)點(diǎn)的聚類，可以得到此時(shí)的聚類數(shù)m2k。比較m和ki，如果兩者不等，重復(fù)上面過(guò)程。如果m=ki，則所得到的m就是確定的聚類數(shù)，同時(shí)得到相應(yīng)聚類數(shù)下V的行向量聚類。當(dāng)且僅當(dāng)V的第i行為聚類j時(shí)，則原始數(shù)據(jù)點(diǎn)xi為第j類。計(jì)算ki的和得到總的聚類數(shù)k，和聚類結(jié)果?！驹囶}二】假定每一段都有段落中心，段落中心句是與本段中所有其它語(yǔ)句相關(guān)度最高的語(yǔ)句，找段落的中心句。每個(gè)句子看成為一個(gè)文檔，其相關(guān)度的計(jì)算思想如下：設(shè) 為第i個(gè)文檔， 為第i個(gè)文檔對(duì)應(yīng)的第m個(gè)短語(yǔ)，為第i個(gè)文檔中第m個(gè)短語(yǔ)的特征，則文檔與的相關(guān)度為：其中： i= 1， 2 ，3 ，4包含關(guān)系計(jì)算： L為包含關(guān)

6、系存在的層次。概念主類計(jì)算：=1為兩個(gè)概念主類。義原在Taxonomy樹上的距離節(jié)點(diǎn)相似計(jì)算如下：同層相同節(jié)點(diǎn)的計(jì)算 ： 為同層相同節(jié)點(diǎn)數(shù)為同層最大節(jié)點(diǎn)數(shù)是層次數(shù)動(dòng)態(tài)角色domain處理（兩個(gè)det中都存在domain）：=a為相同domain節(jié)點(diǎn)個(gè)數(shù)為兩個(gè)det的最深層兩個(gè)det相同節(jié)點(diǎn)數(shù)與總節(jié)點(diǎn)數(shù)的計(jì)算：=a:相同節(jié)點(diǎn)個(gè)數(shù):第1個(gè)det的節(jié)點(diǎn)數(shù):第2個(gè)det的節(jié)點(diǎn)數(shù)主類義原相的計(jì)算，計(jì)算方法同。懲罰因子： 1；否定關(guān)系 0.3；其它指定關(guān)系 0.35短語(yǔ)特征值（tim） 短語(yǔ)的平均權(quán)重標(biāo)題短語(yǔ)權(quán)重最高， 次標(biāo)題短語(yǔ)權(quán)重次之，內(nèi)容短語(yǔ)權(quán)重最低，專業(yè)短語(yǔ)權(quán)重比普通短語(yǔ)高。t:不重復(fù)短語(yǔ)數(shù)為短語(yǔ)

7、平均頻率 文檔中短語(yǔ)出現(xiàn)的次數(shù)文檔中短語(yǔ)總數(shù)短語(yǔ)平均深度短語(yǔ)第一次出現(xiàn)原短語(yǔ)數(shù)文檔中短語(yǔ)總數(shù)文檔（包含短語(yǔ)）的文檔頻率 包含短語(yǔ)的文檔數(shù)所有文檔總數(shù)【試題三】找qq群的貼主、群主和專家。對(duì)一段時(shí)期的群聊天記錄進(jìn)行分析，將每一個(gè)ID對(duì)應(yīng)的聊天記錄看成是一個(gè)文本，對(duì)所有的文本進(jìn)行分詞；將分詞后的文本依據(jù)單詞的相似性進(jìn)行聚類，得到若干主題類；對(duì)每個(gè)主題進(jìn)行分析，發(fā)貼量最大的ID稱為該主題的貼主，其余的貼稱為貼主的跟隨貼，跟隨貼數(shù)稱貼主的影響因子；占有主題最多的貼主稱為該群這一時(shí)期的群主。設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)與算法，找出貼主與群主，并給出其影響因子。對(duì)不同時(shí)期的同一群的聊天記錄進(jìn)行分析，對(duì)不同時(shí)期的主題

8、進(jìn)行比較，不同時(shí)期內(nèi)相同的主題數(shù)，稱為該群的專業(yè)絕對(duì)系數(shù)，專業(yè)絕對(duì)系數(shù)除以總主題數(shù)(不相同)，稱為該群的專業(yè)相對(duì)系數(shù)，專業(yè)相對(duì)系數(shù)越大，則該群越專業(yè)；在不同時(shí)期內(nèi)相同主題的具有最多的相同貼主數(shù)，則該貼主稱為該主題的專家，設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)與算法，找出該群的若干時(shí)期內(nèi)的所有專家，并給出該群的相對(duì)專業(yè)系數(shù)?！驹囶}四】協(xié)同開發(fā)項(xiàng)目工作組影響力的測(cè)定團(tuán)隊(duì)成員i在團(tuán)隊(duì)網(wǎng)絡(luò)中的影響力用網(wǎng)絡(luò)交往約束Ni來(lái)刻畫，網(wǎng)絡(luò)交往約束Ni越低，則團(tuán)隊(duì)成員i社會(huì)影響力越大。網(wǎng)絡(luò)交往約束Ni由成員交往的概率來(lái)決定，一個(gè)成員的社會(huì)影響力越大，其在相同時(shí)間內(nèi)與其它成員交往的人數(shù)越多，其對(duì)應(yīng)的網(wǎng)絡(luò)交往約束Ni越低，團(tuán)隊(duì)成員i的網(wǎng)

9、絡(luò)交往約束Ni由他與其他成員交往的概率決定：團(tuán)隊(duì)成員i與成員j交往的概率pij規(guī)定為：在規(guī)定時(shí)間段T內(nèi)(假定為單位時(shí)間)i與j交往時(shí)間tij所占的比例： pij=tij/T上圖中：T=1 (成員A、B、C的規(guī)定時(shí)間段是同一時(shí)間段)只與交往，所以認(rèn)為把所有的時(shí)間都用來(lái)與交往了；同時(shí)與、交往，其的時(shí)間由、分配，這里假定為.5。 pAB=0.5/1=0.5 pAC=0.5/1=0.5 pBA=1/1=1 pBC=0 pCB=0 pCA=1/1=1 pCB=0 pBC=0 NA=( pAB+ PAC* pCB)2+ (pAC+ PAB* pBC)2=(0.5+0)2+ (0.5+0) 2=0.5 NB

10、=( pBA+ PBC* pCA)2+ (pBC+ PCA* pAC)2=(1+0)2+ (0+0) 2=1 NC=( pCB+ PCA* pAB)2+ (pCA+ PCB* pBA)2=(0+0)2+ (1+0) 2=1因此，A網(wǎng)絡(luò)交往約束NA最低，因此A的社會(huì)影響力最大。團(tuán)隊(duì)社會(huì)網(wǎng)絡(luò)交往分為種基本類型：一種是一個(gè)成員周圍存在若干個(gè)成員在協(xié)同工作；一種是通過(guò)遠(yuǎn)程電話或視頻交流；一種是通過(guò)短信或QQ等文本形式的交流。前一種我們認(rèn)為是直接協(xié)同，其對(duì)應(yīng)網(wǎng)絡(luò)交往約束為NCi；后兩種我們認(rèn)為是遠(yuǎn)程交互, 其對(duì)應(yīng)網(wǎng)絡(luò)交往約束為NIi。在規(guī)定時(shí)間內(nèi)，團(tuán)隊(duì)成員i與成員j協(xié)同的概率pij規(guī)定為：在規(guī)定時(shí)間段T

11、內(nèi)(假定為單位時(shí)間)i與j協(xié)同時(shí)間tij所占的比例：協(xié)同時(shí)間由手機(jī)藍(lán)牙技術(shù)測(cè)定。在規(guī)定時(shí)間內(nèi)，團(tuán)隊(duì)成員i與成員j交互的概率pij規(guī)定為：在規(guī)定時(shí)間段T內(nèi)(假定為單位時(shí)間)i與j交互時(shí)間tij所占的比例：交互時(shí)間由手機(jī)通話時(shí)間或短信總長(zhǎng)度(字符數(shù))測(cè)定。在團(tuán)隊(duì)項(xiàng)目組所有的成員中，i與NIi最小的成員，稱為最佳協(xié)同員工和最有交流影響力的員工。我將其相關(guān)信息發(fā)送給團(tuán)隊(duì)項(xiàng)目組其他所有的成員，從而改進(jìn)成員的協(xié)作與交流意識(shí)。所要處理的任務(wù)包括判斷語(yǔ)音是否為合理的語(yǔ)音，如靜音或忙音均為不合理語(yǔ)音，雙方對(duì)話音一般為合理語(yǔ)音，對(duì)合理語(yǔ)音時(shí)長(zhǎng)的統(tǒng)計(jì)，對(duì)短信字節(jié)數(shù)的統(tǒng)計(jì)，對(duì)藍(lán)牙探測(cè)到對(duì)象時(shí)長(zhǎng)的統(tǒng)計(jì)等。分布式計(jì)算計(jì)算

12、量的分流主要考慮三個(gè)方面的要求：手機(jī)的電池量及其它場(chǎng)所耗能、網(wǎng)絡(luò)的延遲和需要向絡(luò)傳輸?shù)膯挝粫r(shí)間的數(shù)據(jù)量（數(shù)據(jù)擁塞），這三者都可以實(shí)時(shí)進(jìn)行獲取。將手機(jī)上要處理的任務(wù)T分成若干個(gè)子任務(wù)ti，并決定，哪些任務(wù)在手機(jī)本地執(zhí)行，哪些任務(wù)遠(yuǎn)程執(zhí)行，及在哪里執(zhí)行。若共有n個(gè)子任務(wù)需要執(zhí)行，則需n個(gè)可執(zhí)行的場(chǎng)所，我們先選擇耗能低、網(wǎng)絡(luò)的延遲小、向絡(luò)傳輸?shù)臄?shù)據(jù)量少的場(chǎng)所來(lái)完成任務(wù)。為統(tǒng)一計(jì)算場(chǎng)所的耗能、網(wǎng)絡(luò)的延遲與向絡(luò)傳輸?shù)臄?shù)據(jù)量，需要進(jìn)行去量綱處理，設(shè)場(chǎng)所ck，每一個(gè)子任務(wù)都可能在場(chǎng)所ck進(jìn)行處理(總共有2n個(gè)可能組合選擇)，設(shè)子任務(wù)i在所有場(chǎng)所中進(jìn)行處理對(duì)應(yīng)最小的耗能、網(wǎng)絡(luò)的延遲與向絡(luò)傳輸?shù)臄?shù)據(jù)量分別為em

13、in、lmin與dmin；子任務(wù)i在場(chǎng)所ck處理所時(shí)對(duì)應(yīng)的耗能、網(wǎng)絡(luò)的延遲與向絡(luò)傳輸?shù)臄?shù)據(jù)量分別為ei、li與di，則處理量綱后所對(duì)應(yīng)的無(wú)量綱耗能、網(wǎng)絡(luò)的延遲與向絡(luò)傳輸?shù)臄?shù)據(jù)量分別為uei、uli與udi： 依據(jù)不同的需要，選擇對(duì)應(yīng)的耗能、網(wǎng)絡(luò)的延遲與向絡(luò)傳輸?shù)臄?shù)據(jù)量的不同權(quán)重（we+wl+wd=1），得到統(tǒng)一無(wú)量綱模型：由于uci為負(fù)值，因此選擇uci值大的場(chǎng)所作為子任務(wù)i的處理器。手機(jī)上有三種類型的傳感器si：加速器、藍(lán)牙與話筒。對(duì)傳遞過(guò)來(lái)的每一次感知，對(duì)應(yīng)一個(gè)應(yīng)答ai，若傳遞過(guò)來(lái)的感器數(shù)據(jù)是有效的，則為正向應(yīng)答，否則為負(fù)向應(yīng)答。設(shè)傳感器si的傳遞過(guò)來(lái)的數(shù)據(jù)正確的概率為pi，則其下一次傳遞

14、過(guò)來(lái)的數(shù)據(jù)為正確的數(shù)據(jù)的概率為：（正向應(yīng)答） (負(fù)向應(yīng)答 )其中為反饋因子，其值依據(jù)經(jīng)驗(yàn)調(diào)整。取樣時(shí)，依據(jù)pi來(lái)調(diào)整取樣率，pi越大，信息越有效，取樣間隔應(yīng)當(dāng)越小，反之，信息越無(wú)效，取樣間隔應(yīng)當(dāng)越大。 可采用的系統(tǒng)架構(gòu)為：【試題五】依據(jù)董振東的基于知網(wǎng)的義原語(yǔ)義計(jì)算原理，計(jì)算任意兩網(wǎng)頁(yè)之間的相似度。【基本要求】1.將網(wǎng)頁(yè)進(jìn)行預(yù)處理，得到處理好的文本；2.將處理好的文本進(jìn)行分詞，得到標(biāo)注詞；.3.由義原語(yǔ)義計(jì)算原理，計(jì)算任意兩網(wǎng)頁(yè)之間的相似度?！驹囶}六】請(qǐng)自選一部電影，構(gòu)造該電影中所有人物的自動(dòng)機(jī)，反映人物命運(yùn)狀態(tài)的變遷，并用程序模擬。【試題七】實(shí)現(xiàn)SPSS中的二階段聚類、K中心聚類、判別分析與

15、決策樹分析dll?！驹囶}八】社會(huì)網(wǎng)絡(luò)動(dòng)態(tài)結(jié)構(gòu)測(cè)度定義1 社會(huì)網(wǎng)絡(luò)是物聯(lián)網(wǎng)的一種人類社會(huì)活動(dòng)的抽象，不同的社會(huì)活動(dòng)可以從同一物聯(lián)網(wǎng)中抽象出不同的社會(huì)網(wǎng)絡(luò),時(shí)刻t物聯(lián)網(wǎng)為NT(t)，對(duì)應(yīng)社會(huì)活動(dòng)角色Ri的社會(huì)網(wǎng)絡(luò)為SN(t, Ri)。若有n類社會(huì)活動(dòng)角色，則時(shí)刻t的社會(huì)網(wǎng)絡(luò)為SN(t)= SN(t, R1), SN(t, R2), ，SN(t, Rn)。物聯(lián)網(wǎng)NT時(shí)刻t所對(duì)應(yīng)的社會(huì)網(wǎng)絡(luò)為SN(t)可以看作為n個(gè)分層獨(dú)立的社會(huì)網(wǎng)絡(luò)的疊加。這種分層社會(huì)網(wǎng)絡(luò)動(dòng)態(tài)結(jié)構(gòu)使得對(duì)社會(huì)網(wǎng)絡(luò)的研究得到分解，而不是與以前的研究一樣，不加區(qū)分地進(jìn)行社會(huì)網(wǎng)絡(luò)構(gòu)建。我們把社會(huì)網(wǎng)絡(luò)的分層架構(gòu)稱為社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的獨(dú)立性。定義2

16、時(shí)刻t社會(huì)活動(dòng)角色Ri的社會(huì)網(wǎng)絡(luò)SN(t, Ri)用狀態(tài)圖來(lái)測(cè)度。社會(huì)網(wǎng)絡(luò)SN(t, Ri)對(duì)應(yīng)著一個(gè)狀態(tài)譜圖： SN (t, Ri) = (t, Ri): G (V, E, ST)V為社會(huì)網(wǎng)絡(luò)SN(t, Ri)所對(duì)應(yīng)的角色結(jié)點(diǎn)的集合，這些角色結(jié)點(diǎn)的粒度依據(jù)研究的實(shí)際需要而定，可以是單個(gè)的個(gè)體，可以是一個(gè)團(tuán)體，也可以是其不同粒度的組合，為簡(jiǎn)化，在本研究中只考慮同質(zhì)角色的情況，要么是個(gè)體，要么是同一粒度的團(tuán)體。E為社會(huì)網(wǎng)絡(luò)SN(t, Ri)所對(duì)應(yīng)的聯(lián)系的集合。E測(cè)度了社會(huì)網(wǎng)絡(luò)SN(t, Ri)的拓?fù)浣Y(jié)構(gòu)，一般情對(duì)應(yīng)為有向圖，反映了人與人之間的各種關(guān)系，或團(tuán)隊(duì)與團(tuán)隊(duì)之間的各種關(guān)系。設(shè)角色u,vV，

17、則對(duì)eE有e u,v =<u,v>，e v,u =<v,u>，分別為角色u與角色v的聯(lián)系及角色v與角色u的聯(lián)系。聯(lián)系的性質(zhì)由該社會(huì)網(wǎng)絡(luò)的角色定位決定，一類角色可以對(duì)應(yīng)一種或多種聯(lián)系，比如工作社會(huì)網(wǎng)絡(luò)角色之間的聯(lián)系可以有經(jīng)濟(jì)聯(lián)系、合作聯(lián)系、競(jìng)爭(zhēng)聯(lián)系等，聯(lián)系的粒度決定了研究的實(shí)際需要。ST為社會(huì)網(wǎng)絡(luò)SN(t, Ri) 動(dòng)態(tài)結(jié)構(gòu)所對(duì)應(yīng)的狀態(tài)特征。ST測(cè)度了社會(huì)網(wǎng)絡(luò)SN(t, Ri) 動(dòng)態(tài)結(jié)構(gòu)的相對(duì)于拓?fù)浣Y(jié)構(gòu)獨(dú)立的無(wú)量綱特征，用來(lái)描述社會(huì)網(wǎng)絡(luò)中的社會(huì)網(wǎng)絡(luò)輿情突發(fā)性及其影響、社會(huì)網(wǎng)絡(luò)復(fù)雜規(guī)模、社會(huì)網(wǎng)絡(luò)小世界性、社會(huì)網(wǎng)絡(luò)無(wú)標(biāo)度性、社會(huì)網(wǎng)絡(luò)成員間的相關(guān)程度、社會(huì)成員影響力的大小與真?zhèn)?/p>

18、、社會(huì)網(wǎng)絡(luò)團(tuán)隊(duì)的構(gòu)成及其緊密程度等一般性問題。由狀態(tài)譜圖的測(cè)度可知，時(shí)刻t的社會(huì)網(wǎng)絡(luò)SN(t, Ri)對(duì)應(yīng)社會(huì)網(wǎng)絡(luò)流中的一個(gè)狀態(tài)，隨著時(shí)間的變化，社會(huì)網(wǎng)絡(luò)SN(t, Ri)的結(jié)構(gòu)及其特征值也對(duì)應(yīng)著變化，這就是社會(huì)網(wǎng)絡(luò)SN(Ri)的演化。社會(huì)網(wǎng)絡(luò)SN(t, Ri) 狀態(tài)簡(jiǎn)稱t時(shí)刻社會(huì)網(wǎng)絡(luò)，或t時(shí)刻狀態(tài)。由于t時(shí)刻狀中的狀態(tài)特征是相對(duì)于拓?fù)浣Y(jié)構(gòu)獨(dú)立的無(wú)量綱特征，這些t時(shí)刻不同社會(huì)活動(dòng)角色對(duì)應(yīng)的社會(huì)網(wǎng)絡(luò)的狀態(tài)特征可以進(jìn)行疊加，得到t時(shí)刻總的社會(huì)網(wǎng)絡(luò)SN(t)的狀態(tài)特征值。如果不同社會(huì)活動(dòng)角色數(shù)n趨于，則得到真實(shí)的人在t時(shí)刻的真實(shí)社會(huì)行為趨向，從這個(gè)意義上講，我們的社會(huì)網(wǎng)絡(luò)SN(t)只能近似地測(cè)度出人

19、在t時(shí)刻的真實(shí)社會(huì)行為。從整個(gè)時(shí)間線來(lái)看，任一時(shí)刻，社會(huì)網(wǎng)絡(luò)SN(t, Ri)由若干狀態(tài)SN(Ri)構(gòu)成，其狀態(tài)特征可以進(jìn)行疊加；對(duì)同一社會(huì)活動(dòng)角色Rit的社會(huì)網(wǎng)絡(luò)SN(t)的演化過(guò)程，其狀態(tài)特征不停地波動(dòng)向前延伸，整個(gè)社會(huì)網(wǎng)絡(luò)的演化過(guò)程就是粒子波的疊加過(guò)程，這個(gè)性質(zhì)，我們稱之為社會(huì)網(wǎng)絡(luò)SN的波粒二象性。定義3 時(shí)刻t社會(huì)活動(dòng)角色Ri的社會(huì)網(wǎng)絡(luò)SN(t, Ri)的狀態(tài)特征ST為一狀態(tài)特征向量： ST=(, ，C, L/M, r, b, R, Q, k)社會(huì)網(wǎng)絡(luò)密度反映社會(huì)網(wǎng)絡(luò)的稀疏程度，代表社會(huì)網(wǎng)絡(luò)成員的總體緊密程度。社會(huì)網(wǎng)絡(luò)密度定義為網(wǎng)絡(luò)邊數(shù)M與總共可能邊數(shù)N(N-1)/2的比值。無(wú)標(biāo)度指數(shù)

20、反映社會(huì)網(wǎng)絡(luò)的無(wú)標(biāo)度程度。頂點(diǎn)i連接其它頂點(diǎn)的邊的數(shù)目稱為該頂點(diǎn)i的度，頂點(diǎn)i的度用k表示。一個(gè)隨機(jī)選定的節(jié)點(diǎn)其度值恰好為k的概率稱為度k的分布P(k)，對(duì)于一個(gè)具體的網(wǎng)絡(luò)，P(k)表示度值為k的頂點(diǎn)數(shù)目占總頂點(diǎn)數(shù)目的比例。實(shí)際的社會(huì)網(wǎng)絡(luò)的度分布服從冪律形式，即P(k)k-，值越大，則社會(huì)網(wǎng)絡(luò)的無(wú)標(biāo)度程度越大。聚類系數(shù)C反映社會(huì)網(wǎng)絡(luò)集團(tuán)化程度。網(wǎng)絡(luò)中節(jié)點(diǎn)i，設(shè)與其直接相連的節(jié)點(diǎn)數(shù)為ki，這些節(jié)點(diǎn)間實(shí)際存在的邊數(shù)為Mi，總共可能存在的邊數(shù)為，節(jié)點(diǎn)i的聚類系數(shù)Ci定義為： Ci = Mi/。網(wǎng)絡(luò)中所有節(jié)點(diǎn)聚類系數(shù)的平均值稱為平均聚類系數(shù)或整個(gè)網(wǎng)絡(luò)的聚類系數(shù)C。社會(huì)網(wǎng)絡(luò)聚類系數(shù)C越大，則網(wǎng)絡(luò)聚集性越

21、強(qiáng)。平均路徑長(zhǎng)度與網(wǎng)絡(luò)規(guī)模比L/M反映社會(huì)網(wǎng)絡(luò)的小世界性。網(wǎng)絡(luò)中節(jié)點(diǎn)i和節(jié)點(diǎn)j之間最短路徑上的邊數(shù)定義為該節(jié)點(diǎn)對(duì)的最短距離Lij。平均路徑長(zhǎng)度l定義為任意兩個(gè)節(jié)點(diǎn)之間的最短距離的平均值，網(wǎng)絡(luò)規(guī)模用網(wǎng)絡(luò)邊數(shù)M表示，平均路徑長(zhǎng)度與網(wǎng)絡(luò)規(guī)模比L/M隨著社會(huì)網(wǎng)絡(luò)規(guī)模的增大以對(duì)數(shù)尺度增長(zhǎng)，即增長(zhǎng)越來(lái)越小，呈現(xiàn)小世界特性。度同配系數(shù)r用于測(cè)度社會(huì)網(wǎng)絡(luò)的同配性、異質(zhì)性。如果網(wǎng)絡(luò)中的節(jié)點(diǎn)趨于和它近似的節(jié)點(diǎn)相連，例如度大的節(jié)點(diǎn)趨于和度大的節(jié)點(diǎn)相連，則稱該社會(huì)網(wǎng)絡(luò)是同配網(wǎng)絡(luò)；反之，稱之為異配網(wǎng)絡(luò)。社會(huì)網(wǎng)絡(luò)的度同配系數(shù)定義為連在一起的節(jié)點(diǎn)對(duì)應(yīng)的度值的Pearson相關(guān)系數(shù)，即：其中是第i條邊所連接的兩個(gè)節(jié)點(diǎn)的度值(

22、i=1，M,M為總邊數(shù))。r>0，整個(gè)社會(huì)網(wǎng)絡(luò)呈同配結(jié)構(gòu)；r<0，整個(gè)社會(huì)網(wǎng)絡(luò)呈異配結(jié)構(gòu)；r=0，整個(gè)社會(huì)網(wǎng)絡(luò)不相關(guān)。一般地，社會(huì)網(wǎng)絡(luò)r>0。網(wǎng)絡(luò)平均介數(shù)B反映社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的平均影向力。節(jié)點(diǎn)i的介數(shù)定義為：其中g(shù)(m,n)表示節(jié)點(diǎn)m和n之間的最短路徑數(shù)，gi(m,n)表示節(jié)點(diǎn)m和n之間經(jīng)過(guò)節(jié)點(diǎn)i的最短路徑數(shù)。社會(huì)網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)的介數(shù)越大，其在信息傳播過(guò)程中通過(guò)該節(jié)點(diǎn)的信息量越多，其影響力就越大，發(fā)生擁塞的可能性也越大。社會(huì)網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)為N，網(wǎng)絡(luò)平均介數(shù)，則網(wǎng)絡(luò)中的各節(jié)點(diǎn)的平均影響力越大?；セ葜笖?shù)R反映有向社會(huì)網(wǎng)絡(luò)無(wú)向程度，定義為有向網(wǎng)絡(luò)中雙向二元組的百分比，即雙向節(jié)點(diǎn)對(duì)(

23、v,w)且(w,v)的數(shù)量與至少具有一條有向邊的節(jié)點(diǎn)對(duì)(v,w)或(w,v)的數(shù)量的比值?；セ葜笖?shù)R0,1。設(shè)(v,w)是一條有向邊，若R=0，則(w,v)不存在；若R=1，則(w,v)存在。模塊度Q用來(lái)測(cè)度社會(huì)網(wǎng)絡(luò)的社團(tuán)性，社會(huì)網(wǎng)絡(luò)由若干個(gè)較為明顯的社團(tuán)構(gòu)成，社團(tuán)內(nèi)部節(jié)點(diǎn)間連接相對(duì)比較緊密，而社團(tuán)之間連接比較稀疏，設(shè)社會(huì)網(wǎng)絡(luò)劃分為m個(gè)社團(tuán)，eij為網(wǎng)絡(luò)中連接兩個(gè)不同社團(tuán)i、j的節(jié)點(diǎn)的邊在所有邊中所占的比例，表示網(wǎng)絡(luò)中邊接所有社團(tuán)內(nèi)部各節(jié)點(diǎn)的邊在所有邊中所占的比例，表示與第i個(gè)社團(tuán)中的節(jié)點(diǎn)相連的邊在所有邊中所占的比例，其模塊度。一般以Q=0.3作為網(wǎng)絡(luò)具有明顯社團(tuán)結(jié)構(gòu)下界?；パa(bǔ)累積分布斜率k用

24、于測(cè)度社會(huì)網(wǎng)絡(luò)活動(dòng)性，即流行度、熱度、吸引度，設(shè)用戶u對(duì)應(yīng)的節(jié)點(diǎn)的度為n(u)，簡(jiǎn)記為n，則其對(duì)應(yīng)的廣義極值分布SED為：其對(duì)應(yīng)的互補(bǔ)累積分布CCDF為：兩邊取對(duì)數(shù)得： 以作為y軸，以x軸，由最小二乘法進(jìn)行線性擬合可求出n0和c的值，其對(duì)應(yīng)的互補(bǔ)累積分布斜率,|k|越大，則社會(huì)網(wǎng)絡(luò)的活動(dòng)性越強(qiáng)，參與交互的節(jié)點(diǎn)越多。以上九個(gè)特征參數(shù)分別從社會(huì)網(wǎng)絡(luò)緊密程度、無(wú)標(biāo)度程度、集團(tuán)化程度、小世界程度、同配程度、影向力、無(wú)向程度、社團(tuán)形成度、吸引度等角度測(cè)度了社會(huì)網(wǎng)絡(luò)的宏觀特征結(jié)構(gòu)，這些參數(shù)以無(wú)量綱特征的方式畫表達(dá)，以保證各社會(huì)網(wǎng)絡(luò)的宏觀特征結(jié)構(gòu)的獨(dú)立可疊加性。本文側(cè)重于社會(huì)網(wǎng)絡(luò)宏觀特征的動(dòng)態(tài)演化研究，對(duì)社

25、會(huì)網(wǎng)絡(luò)內(nèi)部各結(jié)點(diǎn)的具體狀態(tài)變化，我們另作研究。定義4 社會(huì)網(wǎng)絡(luò)SN(t, Ri)的社團(tuán)依據(jù)對(duì)人們的主觀作用分為兩類，一類為積極社團(tuán)，一類為消極社團(tuán)，積極社團(tuán)反映社會(huì)網(wǎng)絡(luò)中人與人的協(xié)作共進(jìn)；消極社團(tuán)反映社會(huì)網(wǎng)絡(luò)中人與人的破壞與攻擊，包括惡意詆毀，如垃圾郵件社團(tuán)、網(wǎng)絡(luò)炒作社團(tuán)等。積極社團(tuán)定義為一準(zhǔn)完全子圖，設(shè)S為一個(gè)完全子圖，為節(jié)點(diǎn)u對(duì)節(jié)點(diǎn)v的依賴取值，節(jié)點(diǎn)u的k近鄰集合kNN(u)是節(jié)點(diǎn)u在社會(huì)網(wǎng)絡(luò)G中最近的k個(gè)節(jié)點(diǎn)：對(duì)節(jié)點(diǎn)集,若，則S為一個(gè)k近鄰積極社團(tuán)；若，|S|為社團(tuán)S中節(jié)點(diǎn)的數(shù)量，為比例系數(shù)，則S為一個(gè)準(zhǔn)積極社團(tuán)。消極社團(tuán)定義為一普通有向圖S，為節(jié)點(diǎn)u對(duì)節(jié)點(diǎn)v的依賴取值，節(jié)點(diǎn)u的k近鄰集

26、合kNN(u)是節(jié)點(diǎn)u在社會(huì)網(wǎng)絡(luò)G中最近的k個(gè)節(jié)點(diǎn)：對(duì)節(jié)點(diǎn)集,若，則S為一個(gè)以u(píng)為中心的k近鄰消極社團(tuán)。【試題九】基于灰色聚類模型的實(shí)驗(yàn)成績(jī)?cè)u(píng)定實(shí)驗(yàn)采用灰色聚類模型對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)定。用預(yù)習(xí)實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)操作、安全操作、實(shí)驗(yàn)報(bào)告作為本模型的4個(gè)指標(biāo)?；翌惣?jí)別為：優(yōu)、良、中、及格、不及格。算法中指定了各指標(biāo)的相對(duì)重要性權(quán)重。1. 考查指標(biāo)體系的確定本模型的4個(gè)指標(biāo)為：預(yù)習(xí)實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)操作、安全操作、實(shí)驗(yàn)報(bào)告。灰類級(jí)別為：優(yōu)、良、中、及格、不及格。確定各指標(biāo)的相對(duì)重要性權(quán)重：2. 給出j指標(biāo)k子類的白化權(quán)函數(shù) 灰類k= k1，k2,k3,k4,k5)=優(yōu)，良，中，及格，不及格)優(yōu)采用上限測(cè)度白化權(quán)函數(shù)表示(如圖1所示)，良、中、及格采用適中測(cè)度白化權(quán)函數(shù)表示(如圖2所示)，不及格采用下限測(cè)度白化權(quán)函數(shù)表示(如圖3所示)根據(jù)要求，優(yōu)不大于25 ，中和及格不小于25 ，并根據(jù)學(xué)生成績(jī)總體分布情況確定各指標(biāo)灰類劃分標(biāo)準(zhǔn)，即確定灰色白化權(quán)函數(shù)的轉(zhuǎn)折點(diǎn)優(yōu)和不及格的白化權(quán)函數(shù)轉(zhuǎn)折點(diǎn)記為x(1) x(2)，良、中和及格的白化權(quán)函數(shù)轉(zhuǎn)折點(diǎn)則記為x (1) x(2) x(3)。各個(gè)白化權(quán)函數(shù)圖如下：