cdlib.algorithms.l1_ppr

cdlib.algorithms.l1_ppr(g_original: object, seeds: list, min_comm_size: int = 3, max_comm_size: int = 50, alpha: float = 0.85, epsilon: float = 0.0001) → NodeClustering

L1-regularized Personalized PageRank seed expansion.

The algorithm runs the local push approximation of Personalized PageRank from a seed set, then sweeps the degree-normalized scores to extract the most locally coherent community.

Supported Graph Types

Undirected	Directed	Weighted
Yes	No	Yes

Parameters:

• g_original – a networkx graph

• seeds – node list used as personalization seeds

• min_comm_size – minimum community size, default 3

• max_comm_size – maximum community size, default 50

• alpha – damping parameter, default 0.85

• epsilon – local push threshold, default 1e-4

Returns:

NodeClustering object

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.l1_ppr(G, [0, 2, 3], min_comm_size=3, max_comm_size=10)

References:

1. Andersen, R., Chung, F., & Lang, K. Local Partitioning for Graphs. Internet Mathematics, 3(3), 2006.

2. Fountoulakis, K., Roosta-Khorasani, F., Shun, J., Lian, X., & Mahoney, M. W. ell_1-regularized Personalized PageRank for Local Community Detection. arXiv:1602.01886.