2025年大學(xué)《信息與計(jì)算科學(xué)》專業(yè)題庫(kù)——信息與計(jì)算科學(xué)的社交網(wǎng)絡(luò)分析考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每題3分，共15分）1.在社交網(wǎng)絡(luò)分析中，用于衡量節(jié)點(diǎn)之間連接緊密程度的指標(biāo)是（）。A.度中心性B.接近中心性C.中介中心性D.緊密性系數(shù)2.小世界網(wǎng)絡(luò)模型通常具有的特點(diǎn)是（）。A.網(wǎng)絡(luò)密度高，平均路徑長(zhǎng)度短B.網(wǎng)絡(luò)密度低，平均路徑長(zhǎng)度長(zhǎng)C.網(wǎng)絡(luò)密度高，平均路徑長(zhǎng)度長(zhǎng)D.網(wǎng)絡(luò)密度低，平均路徑長(zhǎng)度短3.下列哪種算法通常用于發(fā)現(xiàn)社交網(wǎng)絡(luò)中的社群結(jié)構(gòu)？（）A.Dijkstra算法B.Floyd-Warshall算法C.PageRank算法D.Louvain算法4.在一個(gè)無(wú)向無(wú)權(quán)圖中，節(jié)點(diǎn)的度中心性是指（）。A.節(jié)點(diǎn)連接的邊的數(shù)量B.節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑長(zhǎng)度之和C.節(jié)點(diǎn)之間最短路徑的平均長(zhǎng)度D.節(jié)點(diǎn)所在社群的大小5.社交網(wǎng)絡(luò)分析在信息傳播研究中的應(yīng)用主要體現(xiàn)在（）。A.分析用戶畫(huà)像B.識(shí)別關(guān)鍵意見(jiàn)領(lǐng)袖C.推薦商品或服務(wù)D.以上都是二、填空題（每空2分，共20分）1.社交網(wǎng)絡(luò)可以抽象為由______和______構(gòu)成的圖模型。2.衡量整個(gè)網(wǎng)絡(luò)連通性的指標(biāo)是______。3.節(jié)點(diǎn)的介數(shù)中心性越高，表示該節(jié)點(diǎn)位于網(wǎng)絡(luò)中______的可能性越大。4.隨機(jī)圖模型ER模型是指當(dāng)圖中任意兩個(gè)節(jié)點(diǎn)之間以概率______相連時(shí)生成的圖。5.社群發(fā)現(xiàn)的目標(biāo)是將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為若干個(gè)______，使得社群內(nèi)部連接緊密，社群之間連接稀疏。6.計(jì)算圖中所有節(jié)點(diǎn)對(duì)之間的最短路徑，常用______算法和Floyd-Warshall算法。三、計(jì)算題（每題10分，共30分）1.給定一個(gè)無(wú)向無(wú)權(quán)社交網(wǎng)絡(luò)圖G，其鄰接矩陣如下（0表示無(wú)邊，1表示有邊）：```ABCDEA01010B10101C01001D10001E01110```請(qǐng)計(jì)算節(jié)點(diǎn)A和節(jié)點(diǎn)C的度中心性、接近中心性（假設(shè)所有路徑長(zhǎng)度為1），以及網(wǎng)絡(luò)G的密度。2.在一個(gè)有向無(wú)權(quán)圖中，節(jié)點(diǎn)A到節(jié)點(diǎn)C存在路徑A->B->C，節(jié)點(diǎn)A到節(jié)點(diǎn)D存在路徑A->C->D，節(jié)點(diǎn)B到節(jié)點(diǎn)D存在路徑B->C->D。請(qǐng)計(jì)算節(jié)點(diǎn)C相對(duì)于節(jié)點(diǎn)A和節(jié)點(diǎn)B的中介中心性（使用基于路徑集的方法）。3.假設(shè)一個(gè)社交網(wǎng)絡(luò)服從無(wú)標(biāo)度網(wǎng)絡(luò)模型，其度分布符合冪律分布P(k)∝k^-γ，其中γ=3。請(qǐng)解釋冪律分布的特征，并說(shuō)明在這樣的網(wǎng)絡(luò)中，度數(shù)最高的節(jié)點(diǎn)（Hub節(jié)點(diǎn)）為什么非常重要。四、簡(jiǎn)答題（每題8分，共24分）1.簡(jiǎn)述圖論中的節(jié)點(diǎn)度中心性、中介中心性和特征向量中心性三個(gè)指標(biāo)的主要區(qū)別和適用場(chǎng)景。2.什么是社區(qū)發(fā)現(xiàn)？請(qǐng)簡(jiǎn)述社區(qū)發(fā)現(xiàn)中常用的模塊度（Modularity）指標(biāo)及其作用。3.請(qǐng)簡(jiǎn)述BFS（廣度優(yōu)先搜索）算法的基本思想，并說(shuō)明其在社交網(wǎng)絡(luò)分析中可能的應(yīng)用場(chǎng)景（例如，查找用戶的朋友圈）。五、應(yīng)用與分析題（共11分）假設(shè)你正在研究一個(gè)在線學(xué)習(xí)平臺(tái)的用戶互動(dòng)網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)代表用戶，邊代表用戶之間曾進(jìn)行過(guò)問(wèn)答或評(píng)論互動(dòng)。你收集了該網(wǎng)絡(luò)的部分?jǐn)?shù)據(jù)，并計(jì)算出網(wǎng)絡(luò)密度為0.15，平均路徑長(zhǎng)度為3.8。請(qǐng)基于這些信息，分析該在線學(xué)習(xí)平臺(tái)的社區(qū)活躍度和信息傳播效率可能存在的問(wèn)題，并提出至少兩種可能的改進(jìn)建議，并簡(jiǎn)要說(shuō)明理由。試卷答案一、選擇題1.D2.D3.D4.A5.D二、填空題1.節(jié)點(diǎn)，邊2.網(wǎng)絡(luò)密度3.關(guān)鍵路徑4.p5.社群（或社區(qū)）6.Dijkstra三、計(jì)算題1.度中心性：節(jié)點(diǎn)A為2，節(jié)點(diǎn)C為2。接近中心性：節(jié)點(diǎn)A為4/3≈1.33，節(jié)點(diǎn)C為4/3≈1.33。網(wǎng)絡(luò)密度：(6條邊/(5節(jié)點(diǎn)*(5-1)/2))=6/10=0.6。2.節(jié)點(diǎn)C相對(duì)于節(jié)點(diǎn)A的中介中心性為0.5（因?yàn)镃出現(xiàn)在A到B的路徑上，也出現(xiàn)在A到D的路徑上，共2條相關(guān)路徑，C位于其中1條，且C不是起點(diǎn)或終點(diǎn)）。節(jié)點(diǎn)C相對(duì)于節(jié)點(diǎn)B的中介中心性為0.5（因?yàn)镃出現(xiàn)在B到A的路徑上，也出現(xiàn)在B到D的路徑上，共2條相關(guān)路徑，C位于其中1條，且C不是起點(diǎn)或終點(diǎn)）。3.解析思路：-冪律分布特征：度數(shù)較高的節(jié)點(diǎn)較少，度數(shù)較低的節(jié)點(diǎn)較多，存在少數(shù)“Hub”節(jié)點(diǎn)擁有非常高的連接度。網(wǎng)絡(luò)具有“胖尾”特性。-Hub節(jié)點(diǎn)重要性：在冪律分布的網(wǎng)絡(luò)中，少數(shù)高度連接的Hub節(jié)點(diǎn)連接了網(wǎng)絡(luò)中的大部分其他節(jié)點(diǎn)，它們?cè)谛畔鞑?、網(wǎng)絡(luò)連通性等方面起著核心作用。找到并影響這些Hub節(jié)點(diǎn)，可以高效地覆蓋整個(gè)網(wǎng)絡(luò)。四、簡(jiǎn)答題1.解析思路：-度中心性：衡量節(jié)點(diǎn)的連接數(shù)量，適用于識(shí)別活躍用戶或信息發(fā)布者。-中介中心性：衡量節(jié)點(diǎn)控制信息流動(dòng)的能力，適用于識(shí)別意見(jiàn)領(lǐng)袖或關(guān)鍵傳播者。-特征向量中心性：衡量節(jié)點(diǎn)連接到的高中心性鄰居的程度，適用于識(shí)別受多人認(rèn)可或影響力較大的節(jié)點(diǎn)。區(qū)別在于衡量節(jié)點(diǎn)影響力的不同維度：數(shù)量（度）、控制（中介）、質(zhì)量（特征向量）。2.解析思路：-社區(qū)發(fā)現(xiàn)：將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為若干個(gè)社群，使得社群內(nèi)部節(jié)點(diǎn)連接緊密（相似度高），社群之間連接稀疏（相似度低）。-模塊度：衡量一個(gè)社區(qū)劃分的好壞程度的指標(biāo)。計(jì)算公式通常涉及社區(qū)內(nèi)部邊的期望數(shù)量與實(shí)際數(shù)量之差，以及整個(gè)網(wǎng)絡(luò)的總邊數(shù)。模塊度值越高，表示該劃分結(jié)果越優(yōu)，即社區(qū)內(nèi)部連接越緊密，社區(qū)間連接越松散。3.解析思路：-BFS基本思想：從起始節(jié)點(diǎn)出發(fā)，先訪問(wèn)所有鄰近節(jié)點(diǎn)，再訪問(wèn)鄰近節(jié)點(diǎn)的鄰近節(jié)點(diǎn)，依此類推，按層次遍歷圖。使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。-應(yīng)用場(chǎng)景：在社交網(wǎng)絡(luò)中，BFS可以從一個(gè)種子用戶出發(fā)，查找其直接好友（一層），然后查找好友的好友（二層），以此類推，可以用來(lái)發(fā)現(xiàn)用戶的朋友圈、查找可接觸的潛在聯(lián)系人、進(jìn)行信息或影響力在一定范圍內(nèi)的傳播模擬等。五、應(yīng)用與分析題解析思路：分析：-網(wǎng)絡(luò)密度0.15較低，說(shuō)明用戶之間互動(dòng)頻率不高，網(wǎng)絡(luò)連接較為稀疏，用戶間關(guān)系鏈可能較長(zhǎng)或不夠緊密，可能導(dǎo)致社區(qū)活躍度不高，信息難以快速擴(kuò)散。-平均路徑長(zhǎng)度3.8相對(duì)合理，結(jié)合低密度看，可能反映了平臺(tái)用戶基數(shù)較大，或者用戶間互動(dòng)模式使得平均需要經(jīng)過(guò)不多步才能連接上，但整體連接的緊密度有待提高。問(wèn)題：社區(qū)活躍度可能偏低，信息跨社區(qū)傳播效率不高。建議：1.鼓勵(lì)用戶互動(dòng)：可以設(shè)計(jì)更多促進(jìn)用戶間問(wèn)答、評(píng)論、點(diǎn)贊、組隊(duì)學(xué)習(xí)等互動(dòng)功能，