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的节点实现。论文<ref name='k-core decomp'>{{Cite| publisher = arXiv| doi = 10.48550/arXiv.cs/0310049| last1 = Batagelj| first1 = V.| last2 = Zaversnik| first2 = M.| title = An O(m) Algorithm for Cores Decomposition of Networks| access-date = 2025-05-20| date = 2003-10-25| url = http://arxiv.org/abs/cs/0310049}}</ref>提出了复杂度为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>