大图社区搜索思维导图
社区搜索的类型与相关内容讲解
树图思维导图提供 大图社区搜索 在线思维导图免费制作，点击“编辑”按钮，可对 大图社区搜索 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：58fd34f487b6a699b546f36a434e6934
思维导图大纲
大图社区搜索思维导图模板大纲
序言
内聚力指标
k-core
每个顶点的度至少为k
core数目
k-core指核心数至少为k
k-truss
每条边都至少包含在该子图的(k-2)个三角形中
truss数目
k-clique
每一对顶点都有一条边
k-ECC
任意移除k-1边后依然连通
内聚力和计算效率
k-clique内聚性最强
每个顶点都与剩余顶点相连
k-truss次之
边上的每一对顶点都必须有k-2个共同的邻居
k-ECC较弱
因为连通,并且每个顶点至少k-1个邻居
k-core最弱
边上的任何一对顶点都可能没有共同邻居
计算效率与结构内聚性存在权衡
基于k-core的社区搜索
无向图
Unbounded
以最小度数根据一组顶点查找具有最小度数的连通子图
全局搜索算法
贪婪计算最密集子图,并迭代删除低度顶点
本地搜索算法
局部CS,以局部扩展的方式
基于索引的算法
ShellStruct索引结构
基于核心嵌套建立的树状结构
从根构建/查询
以最小度数根据一个顶点查找具有最小度数的连通子图
Bound
根据一组顶点Q,大小约束k,良好度函数f,查找最多k个顶点,使得f最大的,包含Q的连通子图
NP-hard的指数级成本
因此提出减少社区规模
基于P1还需要有最少的顶点
根据一组顶点Q,最小度函数f,H*作为全局算法返回结果,找到包含Q的连通子图H,使得f(H*)=f(H)且H最小
首先使用H*尽量减小问题规模进行局部贪心搜索
其次采用斯坦纳树问题的近似算法,从H*中找到子图
有向图
在有向图上简单的执行社区搜索可以是忽略方向,然后执行全局搜索算法
Community Search on Directed graph-CSD
在有向图中,以一个查询顶点q,k,l,查询子图,保证连通子图的入度>=k,出度>=l
迭代剥离顶点,直到每个顶点的出度和入度都满足
基于索引提高效率
Decomposition D-core,而后重新以二维表组合将核到索引中
依赖观察到的嵌套,选择性的保留D-core
基于关键词的归属图
每个顶点都与一组关键词相关联
基于关键词的分布图,一个正整数k,一个顶点q,和一组关键词,返回一组子图H,使得H连通且包含q,core-number>=k,且关键词内聚
枚举关键词的子集
针对每个子集查找子图
输出共享关键词最多的子图
基于反单调属性
更快的完成剪枝
CL-tree索引
按照顶点-关键词-顶点s相关联
两种递增,一种递减算法
基于位置的归属图
空间感知社区SAC搜索
基于地理社会网络图G,正整数k,顶点q,返回一个连通子图包含q,且满足k-core,其中顶点的MCC有最小半径
为了提高效率选择近似算法AppInc/APPAcc
基于AppAcc继续开发更精确的近似
以半径为界限的k-core搜索
地理社交网络G,正整数k,半径r,顶点q,返回连通子图H包含q,且为k-core,子图顶点的MCC都有半径r'<r,且子图为最大子图
类似SAC,但是增加了半径限制.
提出三顶点Triv,但是效率太低
基于二元顶点的Binv
基于旋转圆,效率更高的Rotc,还可以剪枝.
GSGQs具有最小熟人限制的地理社会群体查询
地理社交网络,顶点q,正整数k,空间约束A,返回连通的k核子图,满足空间约束,是最大子图
使用R-Tree索引,满足不同约束需要不同的复杂度
基于CBR,使用SaR-Tree索引提高效率,也开发出更高效的算法
时态图
给定时序图,参数c,t,k,持久社区搜索问题是找到G中最大的(c,t)-持久化k核子图
NP-hard问题:使用剪枝,再设计了时序图缩减算法,再进行搜索
基于影响值的属性图
简单影响力CS
G,两个参数k,r,找到G中前r个k-influential社区子图
G,两个参数k,r,找到G中前r个non-contained-k-influential社区子图
在线搜索算法
迭代移除顶点
向后搜索算法,减小计算成本
局部搜索算法:实例最优
基于索引的算法
树形结构组织k个影响力社区
I/O高效算法
按照权重的递减顺序计算k个有影响力的社区
中心-核心CS
多维影响力CS
给定一个多值图(V,E,X)和一个整数k,从G中找出所有参数为k的天际线群落
SkyLineCS问题:SkyLineCommn2D算法解决二维的
提出空间区分算法来高效寻找
基于配置文件的属性图
给定一个剖面图,一个正整数k,一个查询顶点q,找出一组连通子图的k-coreH包含q,且profile内聚,不是其他H的公共子树
PSC问题:引入了反单调属性,更快执行;同时开发CP-tree索引,重新组织为紧凑的树形结构.继而开发出两种快速PC发现算法
讨论
简单图可以分为有向图和无向图,针对简单图第一项工作可能返回最大k核,但是另外两项工作可能不是,也可能有大小限制
属性图主要针对链接关系和属性,使其更易解释,但是针对不同的属性解决方案也不同.
通常采用在线和基于索引的算法,前者更快,但可能离线
基于K-Clique的社区搜索
K-clique及其变体
y-quasi-k-clique,其中,y可以调整k个顶点的内聚性
k-plex,G中每个顶点都至少有|V|-k个邻居,则符合
基于k-clique的CS
基于k-clique的社区
k-clique component
基于k-clique的CS
无向模拟图G(V,E),一个查询顶点q,一个整数k,一个整数α<=k-1,一个y,找出包含q的所有y-quasi-k-clique组件
(α,y)-OCS的特例就是k-clique组件搜索.通过
精确解:枚举包含查询顶点的y-qyasu-k-cliques,而后以计算框架优化.
近似解决方案:减少搜索空间,有针对的枚举,启发式选择顶点序列
最密集Clique循环社区搜索
给定一个简单无向图G(V,E)和一组查询顶点Q,DCPC搜索问题就是找到包含Q的k值最大的k-clique子图
从最大可能的k开始搜索,继而基于索引在线搜索,继而提出clique adjacency tree,而后提出有序邻接树.提出一种DCPC-索引,与上一种支一起持高效查询
基于k-plex的社区搜索
社会群体查询SGQ
G,一个查询顶点q,三个整数p,s,k,从G中返回一个顶点集合F,使得F有p个顶点,v和q之间的距离最多为s,F中任意顶点最多只能和F中其他k个选项共享一条边,F中顶点到q的总距离最小
SGQ也是NP-hard问题,高效的解决方案是SGSelect,同时STGQ问题也是NP-hard问题
最大k-plex社区查询
G,一组查询顶点Q,一个整数k,返回一个子图H,使得H包含Q,H是k-plex,H最大
MCKPQ:NP-complete问题,使用生成-验证方法,枚举所有的k得到max,继而优化为分支和边界范式,采用剪枝.
最具影响力的社区搜索
G,每条边都有一个影响概率,最具有影响力社区搜索问题是找到一个具有最高影响分值的最大kr-clique社区
NP-hard问题:通过顶点的单个影响力访问顶点,并计算每个顶点的k-clique,用C-Tree提高效率,继而有四种高效搜索算法,减小剪枝
讨论
针对简单图:首个采用quasi-clique,第二个采用k-clique,最后两个基于k-plex
针对属性图
基于K-ECC的社区搜索
最高SMCS
G(E,V),一组查询顶点Q,得到子图H包含Q,且λ(H)最大,且H最大
依次枚举最大的k,从|V|到1找到K-ECC.两种高效的枚举:一种基于图分解,另一种基于随机收缩.还提出了新颖的紧凑型索引,得到MST,继而提出高效的查询算法来解决.
最低和最高限度的SMCS
最小限度SMCS:G(V,E),一组查询顶点Q,返回子图H,使得Q含于H,λ(5)最大,H的顶点数最少
最小限度SCMS:APX-hard问题,
最小SMCS:G(V,E),一组查询顶点Q,返回子图H,使得Q含于H,λ(5)最大,H的顶点数最少
首先计算最大SMCS G',而后迭代改进以确保最小;而后提出扩展-提炼框架来寻找最小SCMS,在提炼框架可优化;可通过连通性和最小性放松约束得到近似解
讨论
找到最大SMCS:MST索引
最小SCMS:效率低
其他基于指标的社区搜索
基于本地模块化的社区搜索
基于查询的密度搜索
基于页面排名的个性化社区搜索
G(V,E),一组查询顶点Q,k,返回一组顶点C,使得Q含于C,C有k个顶点,且这些顶点在PPR向量中对应值最大
参考文献中已有很多高效算法
社区搜索系统
旨在提供一个支持一般图任务的平台
为特定图任务定制
对比分析
简单图分析
在线查询算法/索引构建算法
社区结构内聚性/查询返回结果/动态图
Google图的性能测试
在线查询/建立索引/索引空间/基于索引查询/社区质量
属性图分析
位置,时间,剖面图/关键词图/
相关工作
基于k-truss的社区搜索
简单图
给定一个无向模拟图G(V,E),一个查询顶点q,一个整数k>=2,返回H保证k-truss,H中任意两条边都是三角形相连,H是最大子图
TCC搜索:保证社区的三角形连通,且具有小直径,基于truss也有很好的可分解性
在线搜索算法:大量边访问,效率低
基于TCP索引的搜索算法
设计了三角形连接保留索引:TCP-index,以此为基础开发了一种高效查询算法
基于等价truss索引的搜索算法:k-truss等价索引技术:表示三角形连通性和k-truss一致性
更简洁,更节省空间
最近的truss社区搜索
G,一组查询顶点Q,得到子图H使得Q在H中,H满足连通的k-truss,k最大.H同时有最小直径.
CTC搜索:NP-hard问题,以简单的贪心策略可以得到近似值,可以通过批量删除(剪枝)和局部探索(启发策略)来提高效率
基于关键词的属性图
G,一组查询顶点Q(Vq,Wq),k,d,返回一个H,满足H是一个(k,d)-truss包含Vq,有最大的f(H,Wq).
ATC问题:NP-hard;自顶向下的贪婪算法可以进行搜索;ATindex(采用局部探索)可以提高效率
基于权重的归属图
无向加权图G(V,E,W),参数为k,r,找到具有最大权重的前r个k-truss子图H
枚举不现实,以KEP-index的索引优化,组织成树形结构
讨论
计算K-truss社区
通过添加新型索引来提高效率
找到最接近的社区
两种CS解决方法,考虑关键词和影响值
都是通过在线或基于索引的算法开发的
相关思维导图模板
树图思维导图提供 高校“一站式”学生社区综合管理模式建设提质增效指南 新工院内部学习使用 在线思维导图免费制作，点击“编辑”按钮，可对 高校“一站式”学生社区综合管理模式建设提质增效指南 新工院内部学习使用 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：2c1625f87efaba1fbf93c65a144ba120
树图思维导图提供 钉钉云社区思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 钉钉云社区思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：073cafbb95a48a817259df78771e1bfd
沪公网安备 31011502019485号
上海工商