281
个编辑
更改
跳到导航
跳到搜索
第10行：
第10行： − + 第27行：
第27行： +
→k-core分解的算法实现
== k-core分解的算法实现 ==
== k-core分解的算法实现 ==
剪枝过程（pruning process）是常用的寻找该极大子图的k-core分解算法，通过递归删除网络中度小于k的节点实现。论文[^4]提出了复杂度为O(m)（ m为网络中边的数量）的高效计算每个节点coreness的方法（k-core即为coreness不小于k的节点构成的子图）。算法的思想简单描述为：从度最小的节点开始，检查每个邻居节点的度，如果邻居节点的度更大，则将这条边移除并更新该节点的度，选择下一个度最小的节点重复以上过程。每个节点的coreness为节点最终的度。该算法需要检查网络中的每一条边，因此算法复杂度为O(m)。
剪枝过程（pruning process）是常用的进行k-core分解的算法，通过递归删除网络中度小于k的节点实现。论文[^4]提出了复杂度为O(m)（ m为网络中边的数量）的高效计算每个节点coreness的方法（k-core即为coreness不小于k的节点构成的子图）。算法的思想简单描述为：从度最小的节点开始，检查每个邻居节点的度，如果邻居节点的度更大，则将这条边移除并更新该节点的度，选择下一个度最小的节点重复以上过程。每个节点的coreness为节点最终的度。该算法需要检查网络中的每一条边，因此算法复杂度为O(m)。
具体算法描述如下: </br>
具体算法描述如下: </br>
INPUT: graph G = (V, L) represented by lists of neighbors </br>
INPUT: graph G = (V, L) represented by lists of neighbors </br>
:* netwokx.k_core(G,k)获取网络G的k-core
:* netwokx.k_core(G,k)获取网络G的k-core
:* netwokx.core_number(G) 获取网络G每个节点的coreness
:* netwokx.core_number(G) 获取网络G每个节点的coreness
== k-core分解的理论研究 ==
== k-core分解的理论研究 ==
=== 无关网络k-core分解的特征 ===
=== 无关网络k-core分解的特征 ===