Skip to content

Add clique percolation (node_x_percolation()) #21

Description

@jhollway

Clique percolation (Palla, Derényi, Farkas & Vicsek 2005) finds overlapping
communities: a node can belong to several at once, or to none.

Reference: Nature 435:814-818, https://doi.org/10.1038/nature03607

Why this fits without a new class

node_x_clique() in R/motif_cliques.R already solved this problem. Its
documentation says why (lines 11-14):

Cliques are the strictest notion of a cohesive subgroup, and unlike the
communities returned by node_in_*() functions they overlap: a node may
belong to many cliques at once, or to none. That is why this returns an
incidence table rather than a membership vector.

So clique percolation belongs in the motif family, as
node_x_percolation(), returning a node x community incidence matrix via
make_node_motif(). No class change is needed, and no _pkgdown.yml edit
either, since the reference index already picks up contains("_x_").

Algorithm

node_x_percolation <- function(.data, clique_size = 3)
  1. igraph::max_cliques(graph, min = clique_size).
  2. Build the clique-overlap graph: two cliques are adjacent when they share
    clique_size - 1 nodes. Get the overlaps as tcrossprod() of the clique
    incidence matrix.
  3. igraph::components() of that graph. Each component is one community.
  4. A node belongs to every community holding a clique it is in. Build the node
    x community 0/1 matrix and pass it to make_node_motif().

Reuse

The preparation block at R/motif_cliques.R:46-65 should be factored into a
private helper shared with node_x_clique() rather than copied. It covers the
expect_nodes() coercion, the to_unsigned(keep = "positive") step on a signed
network, and the two-mode trick of connecting nodes that share a partner so that
a biclique becomes an ordinary clique.

Also follow node_x_clique() in calling snet_info() when nothing is found
(R/motif_cliques.R:80).

Test that matters

On a fixture with a known overlap, at least one row of the returned matrix must
sum to more than 1. Without that assertion the test suite would pass on an
implementation that quietly returns a partition.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions