281
个编辑
更改
跳到导航
跳到搜索
第10行：
第10行： − +
→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>