【正文】 210123D i m e n s i o n 11 . 51 . 00 . 50 . 0 0 . 5 1 . 0 1 . 5Dimension 2鄒志仁周智佑周慶山張曉林張琪玉張保明曾民族岳劍波楊廷郊楊沛霆嚴(yán)怡民徐引篪肖自力烏家培王知津王崇德汪冰邱均平秦鐵輝倪波孟廣均馬海群馬費(fèi)成盧泰宏劉植惠李毅冷伏海賴茂生江乃武霍國(guó)慶胡昌平郭俊樊松林董曉英初景利陳光祚E u c l i d e a n d i s t a n c e m o d e lD e r i v e d S t i m u l u s C o n f i g u r a t i o nR聚類分析 :布爾類型數(shù)據(jù)的聚類 ? 匹配表 ? 簡(jiǎn)單匹配系數(shù) (屬性是 對(duì)稱 的 ): ? Jaccard 系數(shù) (屬性是 不對(duì)稱 的 ): ? 或 ? 匹配系數(shù) 失配系數(shù) p da jid ??),(cba a jid ???),(pdbcas u mdcdcbabas u m????0101Object i Object j cba cb jid ?? ??),( 相似系數(shù)的算法 （ 1）相似系數(shù) 設(shè) 和 是第 和 個(gè)樣品的觀測(cè)值，則二者之間的相似 測(cè)度為 : ? ??? ipii xxx , 21 ?ix ),( 21 ?? jpjj xxx ?jxi j? ??? ??????? pkpk jjkiikpk jjkiikijxxxxxxxx1 1221])(][)([))((?其中 （ 2）夾角余弦 夾角余弦時(shí)從向量集合的角度所定義的一種測(cè)度變量之間親疏程度的相似系數(shù)。 ?第四類，圖書(shū)館學(xué)研究。 ?第二類，情報(bào)學(xué)理論。 9812591319. “Political Groups” in the attribute sense do not seem to exist, so Pamp。 run。 output。 x=rannor(0)。 Cluster analysis 聚類分析 Cluster analysis This process is captured in the cluster tree (called a dendrogram) 另一種表述： data random。0 成立和對(duì)一切的 jidd jiij ?.成立和對(duì)于一切的 jiddd kjikij ??常用距離的算法 設(shè) 和 是第 i和 j 個(gè)樣品的觀測(cè)值，則二者之間的距離 為： gpkgjkikij xxd11 )||(?? ???? ?? pk jkikij xxd 1 2)(? ??? ipii xxx , 21 ?ix ),( 21 ?? jpjj xxx ?jx明氏距離 特別，歐氏距離 (1) 明氏距離測(cè)度 (2)絕對(duì)值距離或曼哈頓距離 距離為值差的絕對(duì)值之和 ， 其計(jì)算公式為： ????pkjkikij xxJd1||)((3)切比雪夫距離 距離為值差的絕對(duì)值最大者，其計(jì)算公式為： ||m a x)( jkikij xxJd ??第二步：計(jì)算次遠(yuǎn)的點(diǎn)集；依次重復(fù)。0 成立和對(duì)一切的 jid ij ?。 Cluster analysis 案例：在二維空間的點(diǎn)集，如何分類。 ? A very good reference is the SAS/STAT manual section called, ―Introduction to clustering procedures.‖ (htm) ? (See also Wasserman and Faust, though the coverage is spotty). 聚類方法 ?變量之間的聚類即 R型聚類分析，常用相似系數(shù)來(lái)測(cè)度變量之間的親疏程度。 應(yīng)用：學(xué)術(shù)引文 ? Crane， 1972： 《 無(wú)形學(xué)院（ invisible college） 》 ，研究科學(xué)家之間的交流網(wǎng)絡(luò) ? 合作發(fā)表論文，聯(lián)合指導(dǎo)研究生 ? Gattrell ， 1984 ? 數(shù)據(jù)： 19601978年的地理學(xué)論文 ? 方法：參考和注釋中的引用關(guān)系；同被引；共引 ? 結(jié)論： 49%的論文形成大成分；當(dāng)多元度為 6時(shí)，文獻(xiàn)降低到 7片，構(gòu)成網(wǎng)絡(luò)的核 ? 17次 15次 兩個(gè)核 ?“明星”論文 第六講 位置、角色和聚類分析 裴雷 2022/07/11 南京大學(xué)信息管理學(xué)院暑期課程講義 研究目的 ? 社會(huì)學(xué)意義：是否存在位置認(rèn)同，或角色感？ ? 分類與聚類：圖中是否存在功能相近，結(jié)構(gòu)相似的個(gè)體？ ? A primary interest in Social Network Analysis is the identification of ―significant social subgroups‖ – some smaller collection of nodes in the graph that can be considered, at least in some senses, as a ―unit‖ based on the pattern, strength, or frequency of ties. ? There are many ways to identify groups. They all insist on a group being in a connected ponent, but other than that the variation is wide. A) 圖論方法（ Graph theoretical methods） : 派系及其擴(kuò)展 ?派系 Cliques ?K核 kcores ?M核 Mcore ?K叢 kplexes ?nclan ?Kponents B)程序算法 Algorithmic methods: Standard models: Factions (UCINET) NEGOPY (Richards) KliqueFinder (Frank) RNM, JIGGLE (Moody) Betweeness Centrality (Newman) General Distance amp。一個(gè)典型做法的步驟如下。 ? k叢概念似乎比 n派系概念更體現(xiàn)凝聚力思想，更符合對(duì)派系的想象。 ? 2叢可以不是 2派系。 N個(gè)點(diǎn)的 k叢中，每個(gè)點(diǎn)至少與 (Nk)個(gè)點(diǎn)相鄰接。對(duì)此進(jìn)行一定的約束，要求直徑不大于n，即得到 n宗派 (nclan)的定義。 ? n派系：要求任意兩點(diǎn)之間的距離不大于 n。最大的完備子圖是具有最大尺寸的完備子圖。子圖的尺寸為圖中頂點(diǎn)的數(shù)量。正式的定義為：派系就是圖中最大的完全子圖（或完備子圖）。 中心勢(shì)的計(jì)算 ? 圖中心勢(shì)測(cè)量公式 ? 相對(duì)中心勢(shì) ? 平均中心度的方差 NCCniDDD???? 122)(S核心中心勢(shì) nuclear centralization ?跳躍和界限（斯托克曼和斯奈德茲） ?派系分析 ?存在的問(wèn)題 ? 跳躍是否明顯？ ? 三類區(qū)間能否區(qū)分？ 外圍 邊緣 核心 高中心度 低中心度 中心的存在性 ?絕對(duì)中心和結(jié)構(gòu)中心 ? Christofides 的離心度概念 ? 離心度（ eccentricity）：距離矩陣中該行和列中的最大值；與該點(diǎn)相連的最長(zhǎng)路徑的長(zhǎng)度 ? 具有最低離心度的點(diǎn)為絕對(duì)中心 關(guān)于密度與網(wǎng)絡(luò)規(guī)模的討論 ?圖的半徑（ radius）：離心度 ?圖的直徑：圖中點(diǎn)對(duì)中距離最長(zhǎng)的捷徑長(zhǎng)度 ?圖的周長(zhǎng)：最長(zhǎng)的路徑 ? ρ= l/(4cr3/3d) 案例研究：銀行中心性 ?邁克 .施瓦茨 ?數(shù)據(jù)：美國(guó)大公司數(shù)據(jù)庫(kù) 19621973年間美國(guó) 1131家最大公司所有董事名單，共13574人 ?該文用 1969年的 797家企業(yè) ?方法：頂點(diǎn)分析 ?結(jié)論：伊利諾斯大陸銀行、梅隆國(guó)民銀行、摩根銀行、信孚銀行以及加州聯(lián)合銀行等132家企業(yè)為中心 中心度 應(yīng)用：聲望模型 ?社會(huì)網(wǎng)絡(luò)中行動(dòng)者是不平等的 ?所擁有的資源和信息出現(xiàn)分層 附錄： betweenness的算法分析 ? Ulrik， Branders算法 第五講 成分、核與派系 主要概念 ?子圖（ subgraph） ?派系（ cliques） ?聚類（ clusters） ?成分（ ponents） ?核（ cores） ?圈子（ circles） 成分（ ponent） ?含義：最大關(guān)聯(lián)子圖 ? 子圖內(nèi)聯(lián)通 ? 與子圖外的結(jié)點(diǎn)無(wú)關(guān)聯(lián) ?計(jì)算方法：隨機(jī)選取一點(diǎn)，沿邊遍歷，滾雪球方式獲得 ?理解： ? 成分是點(diǎn)集 ? 圖中可能有多個(gè)成分 有向圖中的成分 ?強(qiáng)成分（ strong ponent）：構(gòu)成 SC的元素嚴(yán)格按照鏈的方向組織，沒(méi)有任何方向上的變化 ?弱成分（ week ponent）：只需要聯(lián)系存在的最大成分 塊（ block）與環(huán)成分（ cycle ponent） ?塊，埃弗斯特（ 19821984） ? 沒(méi)有割點(diǎn)的最大子圖 ?環(huán)成分（斯科特） ? 環(huán)：至少有三個(gè)節(jié)點(diǎn)組成的閉合通道，根據(jù)環(huán)的長(zhǎng)度來(lái)表明 3環(huán)， 4環(huán)，及 k環(huán) ? 環(huán)成分：相互交叉的環(huán)構(gòu)成的集合 基于環(huán)成分的聯(lián)系要素分類 ?環(huán)成分 ?懸掛點(diǎn)（ hangers） ?橋點(diǎn) ?孤立樹(shù) ?孤立點(diǎn) 有向圖的環(huán) ?強(qiáng)環(huán)成分 ?半環(huán)成分（） ?在懸點(diǎn)（ hangerson）和未懸點(diǎn)（ hangersoff） ?割點(diǎn)的局部中心位臵 成分的輪廓 ——成分的內(nèi)在結(jié)構(gòu) ? 如何區(qū)分出派系中的核心成員和邊緣成員？ ? 嵌套（ nesting） ? 區(qū)分標(biāo)準(zhǔn)：結(jié)點(diǎn)度和線的多元性 ? 分別稱為 k核（ kcore） 。 ?差值越大，則圖中各點(diǎn)中心度分布得越不均衡，則表明該圖的中心勢(shì)越大 ——該網(wǎng)絡(luò)很可能是圍繞最核心點(diǎn)發(fā)散展開(kāi)的。 中心勢(shì) ?找出圖中的最核心點(diǎn)，計(jì)算該點(diǎn)的中心度與其他點(diǎn)的中心度之差。 關(guān)于中心度測(cè)度的幾個(gè)問(wèn)題 ?中間度的計(jì)算相對(duì)復(fù)雜，可以分四步進(jìn)行： ? [1]betweenness proportion，定義網(wǎng)絡(luò)中 Y相對(duì)于（ X,Z）的 中間度比例 為（經(jīng)過(guò) Y的 XZ捷徑條數(shù) /XZ捷徑條數(shù)） ? [2]點(diǎn)對(duì)依賴值（ pair dependency scores）：定義網(wǎng)絡(luò)中 X對(duì) Y的依賴值為 Y對(duì)（ X,）的中間度比例之和 ? [3]建立局部依賴矩陣，其中每個(gè)元素為相應(yīng)行對(duì)相應(yīng)列的依賴值 ? [4]定義網(wǎng)絡(luò)中某點(diǎn)的中間度為該點(diǎn)相應(yīng)列的列和的一半 關(guān)于中心度測(cè)度的幾個(gè)問(wèn)題 ?伯納西茨算法（ Bonacich， 1972,1987） ? 中心度要考慮其他相關(guān)點(diǎn)的中心度 ? 迭代算法： ?伯納西茨一般型 中心勢(shì)和圖的中心 ?為了與點(diǎn)的中心度相區(qū)別，稱圖的中心性質(zhì)為“中心勢(shì)”。 ? 中間度就是用來(lái)衡量網(wǎng)絡(luò)中某個(gè)個(gè)體充當(dāng)這種中間人角色的程度。 ? 內(nèi)接近性 ? 外接近性 例 1： 關(guān)于中心度測(cè)度的幾個(gè)問(wèn)題 ?直接關(guān)系與間接關(guān)系 ? 如何看待距離為 2或大于 2的關(guān)系結(jié)點(diǎn)對(duì)中心性的影響？ 絕對(duì) 整體 A B 關(guān)于中心度測(cè)度的幾個(gè)問(wèn)題 ?中間度（ Betweenness， Burt， 1992） ? 中間度的概念建立在中間人的基礎(chǔ)之上，或者稱之為“掮客”。 一、中心與邊緣 ?―明星” 三類不同的網(wǎng)絡(luò) N3 N2 N1 局部中心度和整體中心度 ?核心點(diǎn)：處在一系列聯(lián)系的核心位置的點(diǎn)，該點(diǎn)與其他點(diǎn)有眾多的直接聯(lián)系。 ?本章首先介紹了中心度、中心勢(shì)概念，重點(diǎn)說(shuō)明了結(jié)點(diǎn)中心度、緊密中心度、間距中心度及其測(cè)量方法。 若 vi與 ej不關(guān)聯(lián) . ???????,0,1,1ij