PaperlayerView exact revision on arXiv

Source-linked AI summary

A dual assortative measure of community structure

Todd D. Kaplan, Stephanie Forrest

arXiv:0801.3290v1physics.data-anphysics.soc-ph

TL;DR

Existing modularity analyzes positive edges but does not account for negative ones. The paper introduces DAMM to incorporate both signs and evaluates its use in community detection. DAMM achieves high communal overlap on generated networks and is demonstrated on synthetic and real-world networks.

  • Problem

    Original modularity analyzes positively weighted edges, while negative-edge information is not accounted for in the community-detection measure.

    Source: §1 · p. 2, §III · p. 8

  • Method

    DAMM combines positive and negative assortativity contributions, and extremal optimization uses it to detect communities.

    Source: §1 · p. 2, B. Optimizing DAMM with the extremal… · p. 3

  • Results

    DAMM optimization yields communal overlap above 0.95 across settings on DA networks and is demonstrated on generated networks and a real-world example.

    Source: §3 · p. 5, §III · p. 8

  • Takeaways & Limitations

    DAMM can analyze networks with solely negative information and improves community detection in networks containing both positive and negative information.

    Source: §III · p. 8

Abstract

from arXiv · show

Current community detection algorithms operate by optimizing a statistic called modularity, which analyzes the distribution of positively weighted edges in a network. Modularity does not account for negatively weighted edges. This paper introduces a dual assortative modularity measure (DAMM) that incorporates both positively and negatively weighted edges. We describe the the DAMM statistic and illustrate its utility in a community detection algorithm. We evaluate the efficacy of the algorithm on both computer generated and real-world networks, showing that DAMM broadens the domain of networks that can be analyzed by community detection algorithms.

I. METHODS

The methods establish positive and negative assortativity as complementary signals for defining community structure, then incorporate both into the DAMM framework. The section also specifies the edge-weight representation and the positive-edge contribution.

1. Positive assortativity

  • Edge weights are represented as e_rs ∈ {−1, 0, 1} for simplicity, with zero indicating no edge; cumulative weights w_ij represent edges between communities.In practice, edge weights may be real numbers.Source: §1 · p. 2
  • The original modularity measure Q+ provides the positive-assortativity foundation for the DAMM.Its community contribution compares within-community edge weight with an expected value based on the community’s share of edge spokes.Source: §1 · p. 2

2. Negative assortativity

  • The DAMM modifies the positive component so that only positive edge weights contribute to a_i, while both signs contribute to total weight T.Negative assortativity treats adversarial edges within a community as undesirable and defines a corresponding negative component.Source: §1 · p. 2, §2 · p. 3

3. Dual assortative modularity measure (DAMM)

The DAMM combines positive and negative assortativity, reducing to original modularity when negative edges are absent. Extremal optimization searches for community divisions, using node-specific DAMM changes to guide migration.

3. Dual assortative modularity measure (DAMM)

  • Without negative edges, the DAMM reduces to the original modularity measure.The DAMM combines the positive and negative assortativity contributions.Source: §3 · p. 3

B. Optimizing DAMM with the extremal optimization algorithm

  • Extremal optimization recursively divides communities, retaining divisions that increase DAMM and halting when no community can be divided profitably.Each division begins with a random two-way partition and migrates nodes between its parts.Source: B. Optimizing DAMM with the extremal… · p. 3

1. Calculating ∆QD

  • Node migration is guided by each node’s exact change in DAMM, ΔQD,u, which biases the search toward immediate improvements.The algorithm ranks these values and probabilistically selects a node using τ-EO.Source: §1 · p. 3

2. Calculating ∆2QD

The method updates node-level DAMM changes after migrations using a cheaper pairwise change calculation. It evaluates detected communities against known communities with communal overlap, a weighted average of node-level Jaccard similarities.

2. Calculating ∆2QD

  • Updating ΔQD,u after a migration can use Δ²QD,um at O(1) cost instead of recomputing ΔQD,u at O(|Ci|).The pairwise change tracks how migrating node m changes the DAMM change associated with node u.Source: §2 · p. 4

C. Measuring communal overlap

  • Communal overlap is the weighted average of node-level Jaccard indices comparing known and detected communities; Ω = 1 denotes a perfect match.Higher Ω indicates greater similarity between the community configurations.Source: C. Measuring communal overlap · p. 4

II. EXPERIMENTAL RESULTS

The experiments test whether DAMM recovers prescribed communities in generated networks containing positive and negative edges. They compare dual-assortative networks with networks retaining only positive or only negative edges.

1. Generating networks stochastically

  • Networks have 64 nodes in four equal communities; positive intra-community edges have weight 1 and negative inter-community edges have weight −1.Source: §1 · p. 4

2. Experimental setup

  • The first experiment holds zcum = zin + zout at 16, varies zin and zout inversely, and compares each dual network with versions retaining only positive or only negative edges.For each parameter setting, the authors generated 100 networks and assessed communal overlap after DAMM optimization.Source: §2 · p. 4

3. Results

  • Removing positive edges has a larger deleterious effect than removing negative edges: the mean overlap distances from dual-assortative results are 0.50 and 0.084, respectively.Source: §3 · p. 5
  • Across settings, dual-assortative overlap stays above 0.95; positive-only overlap exceeds 0.95 for zin ≥ 4, while negative-only overlap does so only at zout = 16 and falls below 0.5 for zout ≤ 10.The comparison uses 100 independent computer-generated networks per setting.Source: Figure 2 · p. 5, §3 · p. 5

B. Experiment II: the impact of false positives and false negatives

The experiment adds false positive or false negative edges separately to generated dual-assortative networks and measures how network composition affects community recovery. Increasing either intra- or inter-community connectivity lessens the damage from these errors, with different effects on their relative impact.

B. Experiment II: the impact of false positives and false negatives

1. Generating false positives and false negatives

  • False positives are sampled from unused negative-edge space, and false negatives are added as negative edges between same-community nodes.Source: §1 · pp. 5–6

2. Experimental setup

  • The authors generate 40 networks per setting, varying either f+ or f− from 0 to 8 while keeping the other error type absent.The three base settings are (5,16), (7,16), and (5,22).Source: §2 · p. 6

3. Results

  • At (zin = 5, zout = 16), f+ < 3 and f− < 3 keep mean overlap above 0.95; beyond that range detection suffers, and M = 0.67.Source: §3 · p. 6
  • At (zin = 7, zout = 16), overlap exceeds 0.95 for f+ < 6 and f− < 4, while M rises from 0.67 to 0.82 and curve separation from 0.058 to 0.113.Source: §3 · p. 6
  • At (zin = 5, zout = 22), M is 0.79 versus 0.67 at zout = 16, while curve separation is 0.069 versus 0.058.Source: §3 · p. 6
  • Across settings, increasing either zin or zout lessens the damage from false edges, but increasing zin widens the separation between false-positive and false-negative curves more than increasing zout.Source: §3 · p. 6

C. Experiment III: 2005 National Football League schedule

The third experiment applies DAMM to partial representations of the 2005 NFL schedule-correlation network. It compares detected communities with known optimal configurations, but the supplied passages do not report the experiment’s outcomes.

C. Experiment III: 2005 National Football League schedule

  • The NFL network represents teams as nodes and schedule correlations as positive or negative edges; the full network is dual-assortative, while each test network contains only a subset of possible edges.Source: C. Experiment III: 2005 National… · p. 6
  • The comparison reference comprises four optimal three-community alignments and two near-optimal four-community alignments identified for the fully connected network.Source: C. Experiment III: 2005 National… · p. 7
  • The reference alignments contain both positive edges crossing communities and negative edges within communities, matching the experiment’s false-positive and false-negative categories.Source: C. Experiment III: 2005 National… · p. 7

1. Generation of networks

  • For each partial network, the authors optimize DAMM, compare the detected alignment with known optimal configurations, and record the best communal-overlap score.Source: §1 · p. 7
  • Partial networks sample positive edges with probability p+ and negative edges with probability p− = 1 − p+; stochastic sampling can leave nodes with different degrees and make some harder to classify.Source: §1 · p. 7

2. Experimental setup

The experiments test DAMM on partial networks across positive- and negative-edge thresholds, and the results show that using both edge types yields equal or higher overlap than using either alone. The paper concludes that DAMM extends community detection to networks with negative or mixed-sign information.

2. Experimental setup

  • The setup varies p+ and p− from 0 to 1, generates 40 partial networks per threshold pair, and separately optimizes DAMM on DA, PA, and NA networks.Source: §2 · p. 7

3. Results

  • Across mixed-edge settings, DA optimization achieves higher mean communal overlap than PA or NA optimization; the mean gaps are 0.20 units from PA and 0.34 from NA.The only equalities occur in the exclusively positive and exclusively negative settings, where DA matches the corresponding single-edge network.Source: §3 · p. 8, Figure 4 · p. 8
  • Across the experiment, DA optimization yields equal or higher mean communal overlap than PA or NA optimization for each (p+, p−) setting.Each data point averages results from 40 independent randomly generated partial networks with the prescribed thresholds.Source: §3 · p. 8

III. SUMMARY AND CONCLUSIONS

  • DAMM assesses community structure using both positively and negatively weighted edges, extending the friendship-network framing to include adversarial relationships.Source: §III · p. 8
  • The authors demonstrate DAMM on stochastic synthetic networks and a real-world example based on the 2005 NFL schedule.Source: §III · p. 8
  • DAMM supports analysis of networks with only negative information and improves detection in mixed-sign networks, including networks weighted by signed similarity measures such as correlation.Source: §III · p. 8

APPENDIX A: DERIVATION OF ∆QD,u

Appendix A derives the change in DAMM when a node moves between communities by expressing DAMM as a sum of local community contributions. Because only the gain and loss communities change, the derivation focuses on their positive- and negative-edge contributions.

APPENDIX A: DERIVATION OF ∆QD,u

  • DAMM is written as the sum of local contributions from all communities, with positive and negative edge contributions grouped separately.The derivation compares the value before a move with the value after moving node u.Source: Appendix A · pp. 8–9
  • Moving one vertex changes only its gain and loss communities, so only their local DAMM contributions enter the change calculation.The other communities' local contributions remain unchanged.Source: Appendix A · p. 9
  • For the positive-edge gain contribution, the move adds the node's links to the gain community and its positive degree to that community's totals.The cumulative intra-community edge weight increases by the node-to-community edge weight, while the community total increases by the node's positive degree.Source: Appendix A · p. 9
  • The appendix treats negative-edge contributions separately, using the node's negative links to the gain community and its negative degree.The passage identifies these quantities as the cumulative negative edge weight connected to the node and the node's negative degree.Source: Appendix A · p. 9

APPENDIX B: DERIVATION OF ∆2QD,um

Appendix B derives how DAMM's change for moving node u is updated when node m has already moved. It tracks resulting changes to positive-edge terms for the gain and loss communities and treats negative-edge contributions similarly.

APPENDIX B: DERIVATION OF ∆2QD,um

  • The derivation defines the change for moving u conditional on m having already moved, distinguishing it from the change under the current configuration.It first develops the positive-edge contribution and then applies a similar approach to the negative-edge contribution.Source: Appendix B · p. 10
  • After m moves, the positive weight connecting u to the gain and loss communities changes according to the move direction and the edge weight between m and u.The gain-community weight changes by D times that edge weight, while the loss-community weight changes by its opposite.Source: Appendix B · p. 10
  • The positive-weight totals of the gain and loss communities also change with m's move, by the corresponding direction-weighted positive degree.These updated totals feed into the second term of the positive-edge expression.Source: Appendix B · p. 10

Related papers

Loading 0801.3290v1…