Bases: object
Computes an approximate PageRank vector from a given seed.
G (networkit.Graph) – Graph in which an APR is computed.
alpha (float) – Loop probability of random walk.
epsilon (float) – Error tolerance.
Approximate PageRank vector from seeds with parameters specified in the constructor.
seeds (int or list(int)) – The seed node or list of seed nodes.
List of pairs of nodes and scores with positive PageRank.
list(tuple(int, float))
Bases: SelectiveCommunityDetector
The CliqueDetect algorithm. It finds the largest clique in the seed node’s neighborhood.
The algorithm can handle weighted graphs. There, the clique with the highest sum of internal edge weights is returned. This sum includes edge weights to the seed node(s) to ensure that cliques that are well-connected to the seed node(s) are preferred.
For multiple seed nodes, the resulting community is a clique iff the seeds form a clique. Otherwise, only the added nodes form a clique that is fully connected to the seed nodes.
See also: Hamann, M.; Röhrs, E.; Wagner, D. Local Community Detection Based on Small Cliques. Algorithms 2017, 10, 90. https://doi.org/10.3390/a10030090
G (networkit.Graph) – The input graph.
Bases: SelectiveCommunityDetector
Bases: SelectiveCommunityDetector
Produces a cut around a given seed node using the GCE algorithm. It greedily adds nodes from the shell to improve community quality.
G (networkit.Graph) – The input graph, must be unweighted.
Q (str) – The quality function. Supported values: “M” or “L”.
Bases: SelectiveCommunityDetector
Local version of the LFM algorithm as introduced in:
Lancichinetti, A., Fortunato, S., & Kertész, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015. https://doi.org/10.1088/1367-2630/11/3/033015
Their algorithm detects overlapping communities by repeatedly executing this algorithm for a random seed node that has not yet been assigned to any community.
The algorithm has a resolution parameter alpha. A natural choice for alpha is 1, the paper states that values below 0.5 usually give a community containing the whole graph while values larger than 2 recover the smallest communities.
Bases: SelectiveCommunityDetector
The local community expansion algorithm optimizing the T measure.
This implements the algorithm published in:
Fagnan, J., Zaiane, O., & Barbosa, D. (2014). Using triads to identify local community structure in social networks. In 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) (pp. 108–112). https://doi.org/10.1109/ASONAM.2014.6921568
G (networkit.Graph) – Graph in which the community shell be found.
Bases: SelectiveCommunityDetector
The Local Tightness Expansion (LTE) algorithm.
The algorithm can handle weighted graphs.
This is the local community expansion algorithm described in
Huang, J., Sun, H., Liu, Y., Song, Q., & Weninger, T. (2011). Towards Online Multiresolution Community Detection in Large-Scale Networks. PLOS ONE, 6(8), e23829. https://doi.org/10.1371/journal.pone.0023829
G (networkit.Graph) – Graph in which the community shell be found.
alpha (float, optional) – Tightness coefficient - smaller values lead to larger communities. Default: 1.0
Bases: SelectiveCommunityDetector
Produces a cut around a given seed node using the PageRank-Nibble algorithm. see Andersen, Chung, Lang: Local Graph Partitioning using PageRank Vectors
G (networkit.Graph) – The input graph, must be unweighted.
alpha (float) – Loop probability of random walk; smaller values tend to produce larger communities.
epsilon (float) – Tolerance threshold for approximation of PageRank vectors.
Bases: SelectiveCommunityDetector
The random BFS community detection baseline: finds a community around a seed node with a given size using a prefix of a BFS order that is selected at random among all possible prefixes.
G (networkit.Graph) – Graph in which the community shall be found.
C (networkit.Cover) – Ground truth communities to get size information from.
Bases: Algorithm
This class evaluates a set found communities against a ground truth cover. Each found community is compared against the communities of the seed node in the ground truth cover.
For each score, the ground truth community is chosen as comparison that maximizes the score. If seeds are not ignored (a parameter of the constructor), then only ground truth communities that contain the given seed are used to compare against.
The calculated scores are:
Precision: the size of the intersection of found and ground truth community divided by the size of the found community, i.e., how much of the found community was an actual match.
Recall: the size of the intersection of found and ground truth community divided by the size of the ground truth community, i.e., how much of the ground truth community was found.
F1 score: the harmonic mean of precision and recall.
Jaccard index: the size of the intersection of found and ground truth community divided by the size of the union of found and ground truth community.
For each score, the range of values is between 0 and 1, where 0 is the worst and 1 the best score.
G (networkit.Graph) – The graph to compare on
groundTruth (networkit.Cover) – The ground truth cover
found (dict(bool : int)) – The found communities, where the keys are the seed nodes and the values are the found nodes.
ignoreSeeds (bool) – If the seed values shall be ignored, i.e. if any ground truth community is a match
Get the (unweighted) average of the F1 score of every found community.
dict(int ` – A dict between community and the (unweighted) average of the F1 score.
` float)
Get the (unweighted) average of the jaccard indices of every found community.
dict(int ` – A dict between community and the (unweighted) average of the jaccard indices.
` float)
Get the (unweighted) average of the precision of every found community.
dict(int ` – A dict between community and the (unweighted) average of the precision.
` float)
Get the (unweighted) average of the recall of every found community.
dict(int ` – A dict between community and the (unweighted) average of the recall.
` float)
Get the F1 score of every found community.
dict(int ` – A dict between seed node and the F1 score of the seed’s community.
` float)
Get the Jaccard index of every found community.
dict(int ` – A dict between seed node and the jaccard index of the seed’s community.
` float)
Get the precision of every found community.
dict(int ` – A dict between seed node and the precision of the seed’s community.
` float)
Get the recall of every found community.
dict(int ` – A dict between seed node and the recall of the seed’s community.
` float)
Bases: object
Abstract base class for a selective community detector.
Detect a community for the given seed node(s).
It expands either a single seed or a whole set of seed nodes into a single community. This is useful if you know multiple nodes that should be part of the community. This method may throw an exception if the particular algorithm does not support multiple seeds but you specified more than one seed.
seed (int or list(int)) – The seed(s) to find the community for.
The found community as a list of nodes.
list(int)
run(seeds):
Detect one community for each of the given seed nodes.
The default implementation calls expandOneCommunity() for each of the seeds.
seeds (list(int)) – The list of seeds for which communities shall be detected.
dict(int ` – A dict mapping from seed node to community (as a set of nodes).
` int)
Bases: Algorithm
This class calculates the conductance of a set of nodes, i.e., the weight of all edges between the set and the rest of the graph divided by the minimum of the volume (the sum of the weighted degrees) of the community and the rest of the graph.
G (networkit.Graph) – The graph to calculate the conductance on.
community (list(int)) – The list of nodes to calculate the conductance of.
Get the calculated conductance score.
The conductance.
float
Bases: SelectiveCommunityDetector
The Triangle-based community expansion algorithm.
G (networkit.Graph) – graph in which the community shell be found
refine (bool, optional) – If nodes shall be removed again if this improves the quality. Default: True
useJaccard (bool, optional) – If the jaccard index shall be used for weights. Default: False
Bases: SelectiveCommunityDetector
The two-phase local community detection algorithm optimizing the L-measure.
This is an implementation of the algorithm proposed in:
Chen, J., Zaïane, O., & Goebel, R. (2009). Local Community Identification in Social Networks. In 2009 International Conference on Advances in Social Network Analysis and Mining (pp. 237–242). https://doi.org/10.1109/ASONAM.2009.14
G (networkit.Graph) – The input graph.