Skip to content

Add link communities (tie_in_community()) #20

Description

@jhollway

Link communities (Ahn, Bagrow & Lehmann 2010) group ties rather than nodes.
Node-level overlap then falls out for free: a node belongs to as many
communities as its ties do.

Reference: Nature 466:761-764, https://doi.org/10.1038/nature09182

Why this fits the package

Because it partitions ties, it is a hard partition, and needs no
overlapping-membership class. It belongs in the tie_* family as
tie_in_community().

Algorithm

  1. For each pair of ties sharing a node, compute the Jaccard similarity of the
    two other endpoints' inclusive neighbourhoods (each node's neighbours plus
    itself).
  2. Single-linkage hierarchical clustering, stats::hclust(method = "single").
  3. Cut the dendrogram at the height that maximises partition density D.
  4. Return make_tie_member(memb, .data).

Partition density

D is a single score for the whole partition, not one per community. Each
community c has its own density, from its m_c ties and the n_c nodes those
ties induce:

D_c = (m_c - (n_c - 1)) / (n_c(n_c - 1)/2 - (n_c - 1))

D is the mean of those, weighted by m_c. So it returns one number, exactly as
net_by_modularity() does, and belongs beside it in the measure_fit family.

Name it net_by_linkdensity(). The obvious name is taken: net_by_density() is
the ratio of ties to possible ties, at R/measure_cohesion.R:28.

A new net_by_*() must also be added to the fit_net roster at
tests/testthat/helper-contract.R:141, or test-measure_registry_contract.R
fails on an uncovered measure.

Cost

The similarity step is O(sum of squared degrees), so it grows badly with a
heavy-tailed degree distribution. Warn above a threshold with snet_warn() and
state the practical limit in a roxygen @section.

Blocked by

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