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