虚拟社区发现技术与方法

姓名：黄丹华学号：015034910056虚拟社区发现技术与方法组织管理信息传播控制信息检索社会安全事件预警信息推荐公共安全事件管控聚集群体社交圈子虚拟社区发现第三章虚拟社区发现技术与方法用于介绍当前流行的社区结构评判数字指标和经典网络数据集。通过优化网络的全局目标函数，搜索网络社区划分的空间，静态的找出最佳的虚拟社区结构。社区发现算法评价体系一静态计算发现算法二社交网络中虚拟社区发现技术与方法主要研究内容包括:第三章虚拟社区发现技术与方法用于介绍当前流行的社区结构评判数字指标和经典网络数据集。通过优化网络的全局目标函数，搜索网络社区划分的空间，静态的找出最佳的虚拟社区结构。基于网络局部拓扑信息，由网络中的节点动态逐步推演，最终形成虚拟社区结构社区发现算法评价体系一静态计算发现算法二动态计算发现算法三社交网络中虚拟社区发现技术与方法主要研究内容包括:算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法用于介绍当前流行的社区结构评判数字指标和经典网络数据集。通过优化网络的全局目标函数，搜索网络社区划分的空间，静态的找出最佳的虚拟社区结构。基于网络局部拓扑信息，由网络中的节点动态逐步推演，最终形成虚拟社区结构社区发现算法评价体系一静态计算发现算法二动态计算发现算法三社交网络中虚拟社区发现技术与方法主要研究内容包括:1、算法划分准确度指标算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法1.模块度：同一社区内部边的比例减去随机网络中同样社区结构下社区内部边的比例的期望值。模块度越大，则社区划分越合理。1(,)22vwvwvwvwkkQAccmm2.NMI：将社区结构和已知节点的社区归属信息作对比，构造混合矩阵，并基于混合矩阵计算出的类信息熵值。NMI越大，社区划分越合理。,......2ln()lnlnijijijijjiijijNnNNNNMINNNNnn3.RandIndex：正确划分入各社区的内部节点对数目与网络节点对的所有组合数目的比值。该值越大，则社区划分越合理。(,)()2nijijNRYY2、社区结构基准图算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法FeatherDN21JetSN90BeescratchDN63SN89NotchNumber1MusTR82MN23WebKnitUpbangDN16QuasiGallatinKringelThumperShmuddelTR88HookTSN103SN4ScabsCrinStripesSN63TR120DoubleZapCCLTSN83ZipfelSN96FishBeakTR77OscarSN100SN9BumperVauMN60CrossTriggerFivePatchbackMN83JonahSMN5PLHaeckselToplessTR99MN105ForkZigRippleflukeWaveWhitetip实际网络基准图人工网络基准图GN人工网络LFR人工网络以某种方式调整社区划分，使得模块度目标函数达到最优化值，即得到最终社区划分结果。1、模块度最优化算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法1234567892.迭代的合并使模块度增量最大的社区3.在模块度取值最大的时候划分网络经典贪心算法1.初始时，每个节点单独作为一个社区612435789通过多目标函数刻画虚拟社区结构特征，借助智能优化/启发式算法等查找最佳社区划分。2、多目标优化算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法基因序列a123456789101112131424512595131212131111连边编号：同社区连边：基因序列b1234567891011121314212134661211121111131基因编码2基因交叉123456789101112131424212565131212131111123456789101112131421513496121112111113基因序列c基因序列d3基因变异123456789101112131424212565131212131111基因序列c基因序列e1234567891011121314242225651312121311114基因解码基于遗传算法的多目标优化通过网络模型节点间的连接模式，假设其节点的聚类结构，利用贝叶斯似然概率最大化推断出最符合网络真实拓扑结构的网络模型，得到真实网络的社区划分。3、基于概率模型的算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法•网络模型的贝叶斯似然概率：ℒ=𝑞𝑖𝑟[ln𝜋𝑟+𝐴𝑖𝑗ln𝜃𝑟𝑗𝑗𝑖𝑟𝜋𝑟：社区𝑟中的节点占整个网络的比例，𝜋𝑟=1𝑛𝑞𝑖𝑟𝑖；𝑞𝑖𝑟：社区𝑟中的节点和节点𝑖连接的概率，𝑞𝑖𝑟=𝜋𝑟𝜃𝑟𝑗𝐴𝑖𝑗𝑗𝜋𝑠𝜃𝑠𝑗𝐴𝑖𝑗𝑗𝑠；𝜃𝑟𝑖：节点𝑖属于社区𝑟的概率，𝜃𝑟𝑗=𝐴𝑖𝑗𝑞𝑖𝑟𝑖𝑘𝑖𝑞𝑖𝑟𝑖。迭代计算参数𝜋𝑟、𝜃𝑟𝑖和𝑞𝑖𝑟的值直到收敛，获得贝叶斯似然概率的最大值。基于混合模型的算法1.初始时，网络模型生成的拓扑结构6124357892.迭代m次后，网络模型生成的拓扑结构6124357893.迭代n次后，网络模型生成拓扑结构。此时网络模型最符合真实的拓扑结构。（nm)612435789社区I社区II对网络节点进行编码描述，通过随机游走在网络上产生最短数据流，代表最佳社区划分结果。4、信息编码算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法•最小描述长度原理：数据中包含的任何规律性都可以用来压缩数据。使用在线社交网络的虚拟社区结构对网络上的信息流进行压缩编码描述。•采用二级编码，分别对社区和节点编码，通过最小化平均编码长度找到网络的最优划分。平均编码长度：𝐿M=𝑞↷𝐻𝒬+𝑝↻𝑖𝐻(𝒫𝑖𝑚𝑖=1Infomap算法仅使用霍夫曼编码的情况，平均码字长度较长。100010101011100100011111110010利用社区结构，使用二级霍夫曼编码的最优情况，平均码字长度较短00100111100001001011101社区I社区II社区I1110001社区II110000针对网络中节点可能同时属于多个团的性质，从初始团出发动态合并属于同一社区的团，直至得到最佳重叠社区划分。1、团（派系）过滤算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法团（Clique）：网络中的完全子图；k团：具有k个节点的完全子图。CPM算法根据处理后的重叠矩阵，划分出两个重叠的3-团社区6124357893-团社区I3-团社区II2.建立该网络的团-团重叠矩阵𝑂=42000231000132000231000123.将矩阵非对角线上小于2的元素和对角线上小于3的元素置0，剩下的非零元素置1𝑂=1100011000001100011000000k=31.找出网络中所有的最大团612435789通过查找网络中的最大派系，迭代的合并相似度最大的子社区，直到最优划分被发现。2、基于相似度的聚合算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法124589763最大派系{1,2,3,4}、{5}、{6,7,8}、{9}融合派系{5}、{6,7,8}融合派系{5,6,7,8}、{9}子社区间相似度公式：最佳社区评判指标：12,,122vwvwvCwCvwkkMAmm,1122iivwvwivCwCvwkkEQAmOOm基于相似度的EAGLE聚合算法为网络中所有的节点赋予不同的标签，设计一个传播规则，标签根据这个规则在网络上迭代传播，直到所有节点的标签传播达到稳定，最后将具有相同标签的节点划分到一个社区中。3、标签传播算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法143298765按照顺序{1,8,6,5,7,3,2,4,9}更新节点标签，每个节点的标签被更新为其最大数量的邻居所具有的标签。LPA算法243298765243297765243297775243297777242297777222297777222277777222277777基于网络的局部结构定义一个健康函数，从一个种子社区开始，迭代扩展该种子社区，直到健康函数的值最优化，形成一个最优的自然社区。4、局部扩展优化算法算法评价体系一静态计算发现算法二动态计算发现算法三第三章虚拟社区发现技术与方法节点的自然社区：具有最大健康度的子图，即向该子图中增加一个新节点或者从该子图中删去一个节点都将降低子图的局部健康度。同理，以节点8为种子，局部扩展出另一个自然社区。LFM算法以节点1为种子，局部扩展找出自然社区。612435789