Force-directed Layout

Overview

Force-directed layout is a graph layout algorithm based on physical simulation that determines node positions by simulating attraction and repulsion forces between nodes. This layout is particularly suitable for displaying complex relationship networks, such as social networks and knowledge graphs.

The force-directed layout automatically calculates and adjusts node positions to maintain appropriate distances between connected nodes while minimizing edge crossings. During the layout process, it simulates a physical system where nodes repel each other like charged particles, and edges connect nodes like springs.

Key features of force-directed layout include:

1. Automatic Arrangement: No need to manually set node positions, the system automatically finds suitable positions
2. Real-time Adjustment: When you drag a node, other nodes will adjust their positions in real-time
3. Flexible Configuration:
   • Can adjust attraction and repulsion forces between nodes
   • Can set edge lengths
   • Can prevent node overlap
4. Animation Effects: Smooth animations during node movement make changes more natural

Core Concepts

Basic Principles of Force-directed Layout

Force-directed layout is a graph layout algorithm based on physical simulation that models nodes and edges as a physical system:

• Nodes are treated as physical particles
• Edges are treated as springs
• The entire system reaches its lowest energy state through physical simulation

Detailed Core Forces

Node Repulsion

• Physical Model: Coulomb’s Law

• Function: Prevents node overlap and ensures more uniform node distribution, where factor and coulombDisScale control the overall strength and range of repulsion.

• Formula:

  • k: Repulsion coefficient (factor / coulombDisScale²)
  • q1,q2: Node strength (nodeStrength)
  • r: Distance between nodes

Edge Attraction

• Physical Model: Hooke’s Law

• Function: Simulates edge tension, moving nodes along edge directions, where edgeStrength and linkDistance control edge “stiffness” and length.

• Formula:

  • ka: Edge attraction strength (edgeStrength)
  • L: Edge length (linkDistance)
  • r: Actual edge length

Centripetal Force

• Physical Model: Newton’s Universal Law of Gravitation

• Function: Attracts nodes toward the canvas center or cluster centers, where gravity and center control gravity strength and center point position

• Formula:

  • G: Gravitational constant (gravity)
  • xc: Center point coordinates (center)
  • mass: Node mass (nodeSize)

Interaction of Three Forces

• Physical Model: Force interactions, generating acceleration
• Function: Repulsion, edge attraction, and centripetal force work together, affecting node movement through acceleration superposition, ultimately reaching the lowest energy state.
• Formula:

Physical System

Node Velocity Formula

• Formula:

  • v: Velocity
  • a: Acceleration
  • dt: Time step (interval)
  • damping: Damping coefficient (damping)

• Function:

  1. Controls node movement stability
  2. Damping coefficient prevents system oscillation
  3. Time step affects displacement per iteration

Node Position Formula

• Formula:

  • x: Node position
  • v: Node velocity
  • dt: Time step (interval)

• Function:

  1. Updates node position based on velocity
  2. Ensures motion continuity
  3. Prevents node overlap through preventOverlap

Cluster Center Calculation

• Formula:

  • n: Number of nodes in cluster
  • (xi​,yi​): Position of each node

• Function:

  1. Calculates cluster center
  2. Centripetal force pulls nodes toward their cluster center
  3. Cluster center can change dynamically

Cluster Strength Calculation

• Formula:

  • s: Cluster strength (clusterNodeStrength)
  • xc​: Cluster center

• Function:

  1. Controls cluster compactness
  2. Higher cluster strength means tighter clusters
  3. Can be dynamically adjusted based on node properties

Mass Effect on Forces

• Formula:

  • a: Acceleration
  • F: Force (repulsion, edge attraction, centripetal force)
  • mass: Node mass

• Function:

  1. Nodes with larger mass move less
  2. Nodes with smaller mass move more
  3. Mass calculation can be customized through getMass

Energy Calculation

• Formula:

  • m: Node mass
  • v: Node velocity

• Function:

  1. Monitors layout convergence
  2. System stabilizes when energy approaches zero

System Convergence Condition

• Formula:

• Function:

  1. Controls iteration count
  2. Stops when movement is below threshold
  3. Can choose between mean, maximum, or minimum through distanceThresholdMode

Force Interaction Diagram

graph TD
    A[Input] --> B[Initialize Parameters];
    B --> C[Build Layout Calculation];
    C --> D[Iterative Calculation];
    D --> E{Converged?};
    E -->|Yes| F[Output Layout];
    E -->|No| G[Calculate Repulsion];
    G --> H[Calculate Edge Attraction];
    H --> I[Calculate Centripetal Force];
    I --> J[Update Velocity];
    J --> K[Update Position];
    K --> D;

Configuration Options

Based on the physical characteristics of force-directed layout, the following configuration options are available:

Basic Configuration

Force-related Configuration

Repulsion Configuration

Edge Attraction Configuration

Centripetal Force Configuration

Clustering Configuration

Performance and Optimization Configuration

Other Configuration

Code Examples

Basic Usage

const graph = new Graph({
  container: 'container',
  layout: {
    type: 'force',
    // Prevent node overlap
    preventOverlap: true,
    // Node size
    nodeSize: 20,
    // Layout width
    width: 800,
    // Layout height
    height: 600,
  },
});

Preventing Node Overlap

const graph = new Graph({
  layout: {
    type: 'force',
    // Prevent node overlap
    preventOverlap: true,
    // Node size
    nodeSize: 20,
  },
});

Force-directed Layout

This example demonstrates how to create a basic force-directed graph using force-directed layout.

import { Graph, NodeEvent } from '@antv/g6';

const data = {
  nodes: [
    { id: 'node1', label: 'Node 1', size: 30 },
    { id: 'node2', label: 'Node 2', size: 20 },
    { id: 'node3', label: 'Node 3', size: 20 },
    { id: 'node4', label: 'Node 4', size: 20 },
    { id: 'node5', label: 'Node 5', size: 30 },
    { id: 'node6', label: 'Node 6', size: 20 },
  ],
  edges: [
    { source: 'node1', target: 'node2' },
    { source: 'node1', target: 'node3' },
    { source: 'node2', target: 'node4' },
    { source: 'node3', target: 'node4' },
    { source: 'node4', target: 'node5' },
    { source: 'node5', target: 'node6' },
  ],
};

const graph = new Graph({
  container: 'container',
  data,
  autoFit: 'view',
  modes: {
    default: ['drag-canvas', 'zoom-canvas'],
  },
  layout: {
    type: 'force',
    // Prevent node overlap
    preventOverlap: true,
    // Node size
    nodeSize: 20,
    // Centripetal force
    gravity: 0.9,
    // Iteration count
    iterations: 100,
  },
  node: {
    style: {
      size: (d) => d.size,
      fill: '#9EC9FF',
      stroke: '#69C8FF',
      label: (d) => d.label,
      labelPlacement: 'center',
      labelFill: '#333',
    },
  },
  edge: {
    style: {
      stroke: '#e2e2e2',
    },
  },
});

graph.on(NodeEvent.CLICK, async (e) => {
  const nodeId = e.target.id;
  graph.updateNodeData([{ id: nodeId, size: 200 }]);
  await graph.render();
});

graph.render();

Key configuration explanations:

• preventOverlap: Enable node overlap detection
• nodeSize: Set node size
• gravity: Set node centripetal force
• iterations: Set layout calculation precision

You can also refer to View Examples for more usage examples.