欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2023101669040
申请人: 杭州电子科技大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种具有共享约束的社区查询系统;其特征在于:包括前端UI、展示层、应用层、算法层和数据层;所述的前端UI通过图形化组件向用户提供社区查询界面;所述的展示层用于进行页面加载性能设计以及查询参数设置、查询结果调节;所述的应用层用于向算法层输入包括最大共享次数α以及目标节点信息,向展示层和前端UI发送查询结果;所述的算法层用于执行数据处理、初始子图构建、k‑truss属性社区发掘以及社区的调整优化的过程;数据层用于封装属性数据、元路径以及异构网络图;

使用该具有共享约束的社区查询系统进行社区查询的方法,包括以下步骤:步骤一、获取目标领域的原始多源异构关系数据,以图的方式构建目标领域的异构网络;异构网络中包含多种不同类型的节点;

步骤二、根据查询要求,设定最大共享次数α和目标节点q;目标节点q为被搜索的对象;

之后,在异构网络上依次进行数据处理、初始子图构建、k‑truss属性社区发掘以及社区的调整优化,获取社区查询的查询结果,具体过程如下:

2‑1.对步骤一构建的异构网络进行数据处理,获取与目标节点q连通的子网络;在子网络上计算各路径的路径优先级Prio(r)的表达式为:C D

Prio(r)=β·f  (r)+(1‑β)·f  (r)C D

其中,f  (r)为路径r的冲突性;β为路径冲突性权重;f  (r)为路径r的两个节点之间的属性距离;

2‑2.根据目标节点q,在步骤一提取的子网络上构建初始子图G,作为满足共享约束的异构图;

2‑3.在步骤2‑2得到的异构图的基础上进行k‑truss属性社区发掘以及社区的调整优化,所得k‑truss属性社区作为查询结果。

2.根据权利要求1所述的一种具有共享约束的社区查询系统,其特征在于:步骤一构建的异构网络中的节点表示目标领域中的实体;异构网络中的节点具有文本型属性和/或数值型属性。

3.根据权利要求1所述的一种具有共享约束的社区查询系统,其特征在于:步骤2‑2的具体过程如下:

2‑2‑1.构建初始为空集的外扩路径集合R,初始时,根据子网络将目标节点q与其邻接点之间的路径加入外扩路径集合R;

2‑2‑2.根据路径的优先级,选择外扩路径集合R中的路径加入初始子图G;

2‑2‑3.在子网络上寻找在本轮加入初始子图G的各邻接节点两两间的连接路径,并加入外扩路径集合R;重复一次步骤2‑2‑2;

2‑2‑4.以执行一次步骤2‑2‑2和步骤2‑2‑3作为一轮初始子图G的更新过程;将上一轮初始子图G的更新过程中加入初始子图G内的各节点作为初始节点;取各初始节点与其邻接点之间的路径作为待外扩路径;将剩余共享次数不为0的待外扩路径加入外扩路径集合R中;

2‑2‑5.重复步骤2‑2‑2至2‑2‑4,直到不再有任何路径能够加入到外扩路径集合R中之后,以所得的初始子图G作为满足共享约束的异构图。

4. 根据权利要求1所述的一种具有共享约束的社区查询系统,其特征在于:步骤2‑1中所述的与目标节点q连通的子网络根据元路径采用广度优先搜索算法获取;步骤2‑1中两个节点之间的属性距离的计算过程如下:子网络上同类型的任意两个节点的各属性类型之间均具有一个属性距离;计算子网络上同类型节点间的不同属性的属性距离;数值型属性的属性距离采用曼哈顿距离计算,文本型属性的属性距离采用Jaccard距离计算;以两个同类D型节点的所有属性类型的属性距离的加权平均值作为该两个同类型节点的属性距离f (u,v);u、v表示同类型的两个节点。

5. 根据权利要求1所述的一种具有共享约束的社区查询系统,其特征在于:步骤2‑1中C所述的路径r的冲突性f  (r)表达式为:

C C

f  (r)=max{f  (v)}

C

其中,f  (v)为路径r上各节点的冲突性;

C

节点的冲突性f  (v)的表达式为:

C

f  (v)=c(v)/l(v)

其中,c(v)为节点v在子网络中被所有路径所经过的次数;l(v)为节点v的剩余可共享次数。

6.根据权利要求3所述的一种具有共享约束的社区查询系统,其特征在于:步骤2‑2‑2的具体过程为:根据路径的优先级对外扩路径集合R内所有路径进行升序排序,每次选择优先级最小的路径加入初始子图G中,直至外扩路径集合R为空;每次将路径加入初始子图G后均更新外扩路径集合R内所有受影响的路径的剩余共享次数、冲突性及优先级;受影响的路径为与被加入初始子图G的路径相交的路径;所有受影响的路径的剩余共享次数均减小1;

路径的剩余共享次数的初始值为最大共享次数α;移除外扩路径集合R内的端点重复路径以及包含剩余共享次数为0的节点的路径;端点重复路径为两个端部节点已在初始子图G通过一条路径直接连接的路径;对从外扩路径集合R内移除的路径进行标记。

7.根据权利要求1所述的一种具有共享约束的社区查询系统,其特征在于:步骤2‑3的具体过程为:(1)在步骤2‑2得到的异构图上进行k‑truss属性社区发掘;根据k‑truss模型,不断删除异构图中属性距离最大的路径并进行k‑truss结构的维护,直至删除属性距离最大的路径后无法维持k‑truss结构时,不再继续删除异构图中属性距离最大的路径,得到k‑truss属性社区;

(2)对k‑truss属性社区进行社区调优;在子网络图中搜索异构图更新路径;删除当前k‑truss社区中属性距离最大的路径,并将异构图更新路径加入k‑truss属性社区;

异构图更新路径满足以下四个条件:

条件1.删除当前k‑truss属性社区中属性距离最大的路径,并将异构图更新路径加入k‑truss属性社区后,依旧维持k‑truss的社区结构;

条件2.异构图上更新路径的剩余共享次数不为0;

条件3.异构图上更新路径的属性距离小于k‑truss属性社区中属性距离最大的路径的属性距离;

条件4.异构图上更新路径未被标记为已经访问;

(3)重复步骤(1)至步骤(3),当子网络图中不存在异构图更新路径时,以最终的k‑truss属性社区作为查询结果。