A Degeneracy Framework for Graph Similarity 论文阅读笔记
A-Degeneracy-Framework-for-Graph-Similarity基本概念
k-core: Theories and applications
度分布(Degree Distribution)
随机选择一个节点度为k的概率
$$ \begin{equation} p_k={n_k\over n}\end{equation} $$
余度分布(Excess Degree Distribution)
Excess degree distribution is the probability distribution, for a node reached by following an edge, of the number of other edges attached to that node. In other words, it is the distribution of outgoing links from a node reached by following a link.
$$ \begin{equation}q_j={(j+1)p_{j+1}\over\sum_{i=0}^\infty kp_k}\end{equation} $$
图退化(Graph Degeneracy)
- k-shell：属于k-core但不属于(k+1)-core的节点构成集合称为k-shell
- coreness k：节点的coreness为 k 等价于此节点在网络的k-shell集中
基本方法
for i = 1 2… (k-1) do:
while there're nodes with degree less than or equal to i in the graph do:
remove all nodes with degree less than or equal to i in the graph
end while
end for
也存在时间复杂度更低的其它高级算法。
论文笔记
A Degeneracy Framework for Graph Similarity