排名

节点排名算法。

属性 scores_ 为图的每个节点分配一个重要性分数。

PageRank

class sknetwork.ranking.PageRank(damping_factor: float = 0.85, solver: str = 'piteration', n_iter: int = 10, tol: float = 1e-06)[source]

每个节点的 PageRank，对应于随机游走访问它的频率。

随机游走以某个固定概率重新开始。用户可以个性化重新开始分布。这种变体被称为个性化 PageRank。

参数：

  • damping_factor (float) – 继续随机游走的概率。

  • solver (str) –

    • 'piteration'，对给定迭代次数使用幂迭代。

    • 'diteration'，对给定迭代次数使用异步并行扩散。

    • 'lanczos'，使用给定容差的特征值求解器。

    • 'bicgstab'，使用给定容差的双共轭梯度稳定化方法。

    • 'RH'，使用 Ruffini-Horner 多项式评估。

    • 'push'，使用给定容差的基于推送的算法

  • n_iter (int) – 某些求解器的迭代次数。

  • tol (float) – 某些求解器收敛的容差。

变量：

  • scores (np.ndarray) – 每个节点的 PageRank 分数。

  • scores_row (np.ndarray) – 行的分数，对于二部图。

  • scores_col (np.ndarray) – 列的分数，对于二部图。

示例

>>> from sknetwork.ranking import PageRank
>>> from sknetwork.data import house
>>> pagerank = PageRank()
>>> adjacency = house()
>>> weights = {0: 1}
>>> scores = pagerank.fit_predict(adjacency, weights)
>>> np.round(scores, 2)
array([0.29, 0.24, 0.12, 0.12, 0.24])

参考文献

Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.

fit(input_matrix: csr_matrix | ndarray, weights: dict | ndarray | None = None, weights_row: dict | ndarray | None = None, weights_col: dict | ndarray | None = None, force_bipartite: bool = False) → PageRank[source]

计算每个节点的 pagerank。

参数：

  • input_matrix (sparse.csr_matrix, np.ndarray) – 图的邻接矩阵或二部邻接矩阵。

  • weights (np.ndarray, dict) – 个性化 PageRank 的重新开始分布的权重。如果为 None，则使用均匀分布（无个性化，默认）。

  • weights_row (np.ndarray, dict) – 个性化 PageRank 的重新开始分布在行上的权重。用于二部图。如果 weights_row 和 weights_col 都是 None（默认），则使用行上的均匀分布。

  • weights_col (np.ndarray, dict) – 个性化 PageRank 的重新开始分布在列上的权重。用于二部图。

  • force_bipartite (bool) – 如果为 True，则将输入矩阵视为二部图的二部邻接矩阵。

返回值：

self

返回类型：

PageRank

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回分数。与 fit 方法相同的参数。

返回值：

scores – 分数。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的分数。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回值：

scores – 分数。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回值：

self

返回类型：

算法

Katz

class sknetwork.ranking.Katz(damping_factor: float = 0.5, path_length: int = 4)[source]

Katz 中心性，定义为

\(\sum_{k=1}^K\alpha^k(A^k)^T\mathbf{1}\)

其中 \(A\) 是邻接矩阵，\(\alpha\) 是阻尼因子，\(K\) 是路径长度。

参数：

  • damping_factor (float) – 路径贡献的阻尼因子。

  • path_length (int) – 路径的最大长度。

变量：

  • scores (np.ndarray) – 每个节点的分数。

  • scores_row (np.ndarray) – 行的分数，对于二部图。

  • scores_col (np.ndarray) – 列的分数，对于二部图。

示例

>>> from sknetwork.data.toy_graphs import house
>>> adjacency = house()
>>> katz = Katz()
>>> scores = katz.fit_predict(adjacency)
>>> np.round(scores, 2)
array([6.5 , 8.25, 5.62, 5.62, 8.25])

参考文献

Katz, L. (1953). 从社会计量分析得出的新地位指数. 心理测量学, 18(1), 39-43.

fit(input_matrix: csr_matrix | ndarray | LinearOperator) → Katz[source]

Katz 中心性。

参数：

input_matrix – 图的邻接矩阵或双邻接矩阵。

返回值：

self

返回类型：

Katz

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回分数。与 fit 方法相同的参数。

返回值：

scores – 分数。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的分数。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回值：

scores – 分数。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回值：

self

返回类型：

算法

HITS

class sknetwork.ranking.HITS(solver: str | SVDSolver = 'lanczos')[source]

每个节点的中心节点和权威节点分数。对于二部图，中心节点分数在行上计算，权威节点分数在列上计算。

参数：

solver ('lanczos' (默认，Lanczos 算法) 或 SVDSolver (自定义求解器)) – 要使用的求解器。

变量：

  • scores (np.ndarray) – 每个节点的中心节点分数。

  • scores_row (np.ndarray) – 每个行的中心节点分数，对于二部图。

  • scores_col (np.ndarray) – 每个列的权威节点分数，对于二部图。

示例

>>> from sknetwork.ranking import HITS
>>> from sknetwork.data import star_wars
>>> hits = HITS()
>>> biadjacency = star_wars()
>>> scores = hits.fit_predict(biadjacency)
>>> np.round(scores, 2)
array([0.5 , 0.23, 0.69, 0.46])

参考文献

Kleinberg, J. M. (1999). 超链接环境中的权威来源. ACM 杂志, 46(5), 604-632.

fit(adjacency: csr_matrix | ndarray) → HITS[source]

使用谱方法计算 HITS 算法。

参数：

adjacency – 图的邻接矩阵或双邻接矩阵。

返回值：

self

返回类型：

HITS

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回分数。与 fit 方法相同的参数。

返回值：

scores – 分数。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的分数。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回值：

scores – 分数。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回值：

self

返回类型：

算法

介数中心性

class sknetwork.ranking.Betweenness(normalized: bool = False)

基于 Brandes 算法的介数中心性。

变量：

scores (np.ndarray) – 每个节点的介数中心性值

示例

>>> from sknetwork.ranking import Betweenness
>>> from sknetwork.data.toy_graphs import bow_tie
>>> betweenness = Betweenness()
>>> adjacency = bow_tie()
>>> scores = betweenness.fit_transform(adjacency)
>>> scores
array([4., 0., 0., 0., 0.])

参考文献

Brandes, Ulrik (2001). 介数中心性的更快算法. 数学社会学杂志.

fit(adjacency: csr_matrix | ndarray) → Betweenness

将算法拟合到数据。

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回分数。与 fit 方法相同的参数。

返回值：

scores – 分数。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的分数。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回值：

scores – 分数。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回值：

self

返回类型：

算法

接近中心性

class sknetwork.ranking.Closeness(method: str = 'exact', tol: float = 0.1)[source]

通过连通图中每个节点的接近中心性进行排名，对应于从该节点到所有其他节点的最短路径的平均长度。

参数：

  • method – 表示结果应该是精确的还是近似的。

  • tol (float) – 如果 method=='approximate'，则每个分数条目允许的容差。

变量：

scores (np.ndarray) – 每个节点的接近中心性。

示例

>>> from sknetwork.ranking import Closeness
>>> from sknetwork.data import cyclic_digraph
>>> closeness = Closeness()
>>> adjacency = cyclic_digraph(3)
>>> scores = closeness.fit_predict(adjacency)
>>> np.round(scores, 2)
array([0.67, 0.67, 0.67])

参考文献

Eppstein, D., & Wang, J. (2001, January). 中心性的快速近似. 在第十二届 ACM-SIAM 离散算法年会论文集 (pp. 228-229). 工业与应用数学学会.

fit(adjacency: csr_matrix | ndarray) → Closeness[source]

连通图的接近中心性。

参数：

adjacency – 图的邻接矩阵。

返回值：

self

返回类型：

Closeness

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回分数。与 fit 方法相同的参数。

返回值：

scores – 分数。

返回类型：

np.ndarray

get_params()

获取参数作为字典。

返回值：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的分数。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回值：

scores – 分数。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回值：

self

返回类型：

算法

后处理

sknetwork.ranking.top_k(scores: ndarray, k: int = 1, sort: bool = True)[source]

返回最高值 k 个元素的索引。

参数：

  • scores (np.ndarray) – 值数组。

  • k (int) – 要返回的元素个数。

  • sort (bool) – 如果为 True，则按值的降序对索引进行排序（最高值的元素排在最前面）。

示例

>>> top_k([1, 3, 2], k=2)
array([1, 2])