{"_id":"ngraph.leiden","_rev":"3-0479d6b8a6012a6839cf7a16dd51168d","name":"ngraph.leiden","dist-tags":{"latest":"0.3.0"},"versions":{"0.1.0":{"name":"ngraph.leiden","version":"0.1.0","keywords":["ngraph","louvain","leiden","graph","community"],"author":{"name":"Andrei Kashcha"},"license":"MIT","_id":"ngraph.leiden@0.1.0","maintainers":[{"name":"anvaka","email":"anvaka@gmail.com"}],"dist":{"shasum":"0fd82e06db779ad0441df5fc88f380fc44a6a089","tarball":"https://registry.npmjs.org/ngraph.leiden/-/ngraph.leiden-0.1.0.tgz","fileCount":32,"integrity":"sha512-4XxBiSJ8SrNyZsLBcDe5Y0rfKPr4JYFo2sadWeGKoJdcWRQc+pmWVZgT7Be2ERFk+IZoMKin3sZaWdaqad7gqQ==","signatures":[{"sig":"MEQCIAfwV95+SnK7x117Ie7WEOa5JVRWeyOd3vjpmKB3HKDDAiASVuB5a30nZxMO5//xb4AP6Jl1LsRtSjm0O63keTJLcA==","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":159653},"main":"dist/ngraph-leiden.cjs.js","type":"module","module":"dist/ngraph-leiden.es.js","exports":{".":{"import":"./dist/ngraph-leiden.es.js","require":"./dist/ngraph-leiden.cjs.js"}},"gitHead":"6f32d5608cb94b6d8bc8ec9b0777246a1c73d9e3","scripts":{"dev":"vite","test":"vitest run","build":"vite build","demo:dev":"vite --config demo/vite.config.js","demo:build":"vite build --config demo/vite.config.js","test:watch":"vitest","demo:preview":"vite preview --config demo/vite.config.js"},"_npmUser":{"name":"anvaka","email":"anvaka@gmail.com"},"_npmVersion":"10.9.0","description":"Leiden/Louvain community detection for ngraph.graph (JS)","directories":{},"_nodeVersion":"22.12.0","dependencies":{"ngraph.graph":"^20.0.1","ngraph.random":"^1.2.0"},"_hasShrinkwrap":false,"devDependencies":{"vite":"^7.1.1","w-gl":"^0.22.0","vitest":"^3.2.4","miserables":"^3.0.0","ngraph.fromdot":"^7.1.0","ngraph.forcelayout":"^3.3.1"},"_npmOperationalInternal":{"tmp":"tmp/ngraph.leiden_0.1.0_1754813496814_0.5204095735356928","host":"s3://npm-registry-packages-npm-production"}},"0.2.0":{"name":"ngraph.leiden","version":"0.2.0","keywords":["ngraph","louvain","leiden","graph","community"],"author":{"name":"Andrei Kashcha"},"license":"MIT","_id":"ngraph.leiden@0.2.0","maintainers":[{"name":"anvaka","email":"anvaka@gmail.com"}],"bin":{"ngraph-leiden":"bin/ngraph-leiden.js","ngraph.leiden":"bin/ngraph-leiden.js"},"dist":{"shasum":"ee7060760266ada157b6427b45a6baed05e63d4f","tarball":"https://registry.npmjs.org/ngraph.leiden/-/ngraph.leiden-0.2.0.tgz","fileCount":36,"integrity":"sha512-2GiI0+sDceAaQv7iGPnhY04u7dLUhPQXiG5ARwZqLTEV+qPa5s3tyBX8QYFoa1gXYuTCZSewM4eLXBKNCImozA==","signatures":[{"sig":"MEUCIQCKkxHjR5viMfFHrfNWo2K3GnEApDEkncXuk5tK8PjzvQIgBh5f8JYicDNJOu69Tq3lm8DkZlndG0fg9Jnyv865evg=","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":184577},"main":"dist/ngraph-leiden.cjs.js","type":"module","module":"dist/ngraph-leiden.es.js","exports":{".":{"import":"./dist/ngraph-leiden.es.js","require":"./dist/ngraph-leiden.cjs.js"}},"gitHead":"71cd0674311ad26b1e60908dacb460a3426c9873","scripts":{"dev":"vite","test":"vitest run","build":"vite build","demo:dev":"vite --config demo/vite.config.js","demo:build":"vite build --config demo/vite.config.js --base=/ngraph.leiden/","test:watch":"vitest","demo:deploy":"sh ./deploy.sh","demo:preview":"vite preview --config demo/vite.config.js","prepublishOnly":"npm run build"},"_npmUser":{"name":"anvaka","email":"anvaka@gmail.com"},"_npmVersion":"10.9.0","description":"Leiden/Louvain community detection for ngraph.graph (JS)","directories":{},"_nodeVersion":"22.12.0","dependencies":{"ngraph.graph":"^20.0.1","ngraph.todot":"^4.1.0","ngraph.random":"^1.2.0","ngraph.fromdot":"^7.1.0"},"_hasShrinkwrap":false,"devDependencies":{"vite":"^7.1.1","w-gl":"^0.22.0","vitest":"^3.2.4","miserables":"^3.0.0","ngraph.forcelayout":"^3.3.1"},"_npmOperationalInternal":{"tmp":"tmp/ngraph.leiden_0.2.0_1754816781709_0.9899488114022446","host":"s3://npm-registry-packages-npm-production"}},"0.3.0":{"name":"ngraph.leiden","version":"0.3.0","description":"Leiden/Louvain community detection for ngraph.graph (JS)","type":"module","main":"dist/ngraph-leiden.cjs.js","module":"dist/ngraph-leiden.es.js","bin":{"ngraph-leiden":"bin/ngraph-leiden.js","ngraph.leiden":"bin/ngraph-leiden.js"},"exports":{".":{"import":"./dist/ngraph-leiden.es.js","require":"./dist/ngraph-leiden.cjs.js"}},"scripts":{"build":"vite build","dev":"vite","test":"vitest run","test:watch":"vitest","prepublishOnly":"npm run build","demo:dev":"vite --config demo/vite.config.js","demo:build":"vite build --config demo/vite.config.js --base=/ngraph.leiden/","demo:deploy":"sh ./deploy.sh","demo:preview":"vite preview --config demo/vite.config.js","bench":"node benchmarks/run.js"},"keywords":["ngraph","louvain","leiden","graph","community"],"author":{"name":"Andrei Kashcha"},"license":"MIT","dependencies":{"ngraph.fromdot":"^7.1.0","ngraph.random":"^1.2.0","ngraph.todot":"^4.1.0"},"devDependencies":{"benchmark":"^2.1.4","miserables":"^3.0.0","ngraph.forcelayout":"^3.3.1","ngraph.louvain":"^2.0.0","vite":"^7.1.1","vitest":"^3.2.4","w-gl":"^0.22.0"},"_id":"ngraph.leiden@0.3.0","gitHead":"d49a175c6a55fbc8ba4198fd3f1b1dfb15ba0251","_nodeVersion":"24.7.0","_npmVersion":"11.5.1","dist":{"integrity":"sha512-cF20r8cnwVnr6V74fPQX8rkeIJ5uEuJ44kOYx+D1V2Bx09JthS9pASXAZ0pt+c8iuEmq4Q4N9dN93bKIOBrVkg==","shasum":"c3b7eebe6388d9302db851592b102a3a955ca8a1","tarball":"https://registry.npmjs.org/ngraph.leiden/-/ngraph.leiden-0.3.0.tgz","fileCount":39,"unpackedSize":216602,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEUCIH5hnLM64mbcqw1tYvuEGpy7SmPoImMiF0uTpevPykzhAiEAkI9/vyylc5A9VPymx3mI+9s2AM8nrpa4B0F0dcbUxNI="}]},"_npmUser":{"name":"anvaka","email":"anvaka@gmail.com"},"directories":{},"maintainers":[{"name":"anvaka","email":"anvaka@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/ngraph.leiden_0.3.0_1780381230562_0.7082597204804619"},"_hasShrinkwrap":false}},"time":{"created":"2025-08-10T08:11:36.813Z","modified":"2026-06-02T06:20:30.821Z","0.1.0":"2025-08-10T08:11:37.016Z","0.2.0":"2025-08-10T09:06:21.901Z","0.3.0":"2026-06-02T06:20:30.716Z"},"author":{"name":"Andrei Kashcha"},"license":"MIT","keywords":["ngraph","louvain","leiden","graph","community"],"description":"Leiden/Louvain community detection for ngraph.graph (JS)","maintainers":[{"name":"anvaka","email":"anvaka@gmail.com"}],"readme":"## ngraph.leiden\n\nLeiden/Louvain community detection for ngraph.graph. Fast, deterministic (seeded), and flexible: undirected/directed modularity, CPM with resolution, multilayer aggregation, fixed nodes, and custom weights/sizes.\n\nQuick online demo: https://anvaka.github.io/ngraph.leiden/\n\nIf you prefer command line: `cat graph.dot | npx ngraph.leiden` - prints node/community membership\n\n## Install\n\nInstall the published package in your project:\n\n```sh\nnpm i ngraph.leiden\n```\n\nThis repository uses Node 18+ for development. To work on the repo locally:\n\n```sh\nnpm install\nnpm test\nnpm run build\n```\n\n## Quick start\n\n```js\nimport createGraph from 'ngraph.graph'\nimport { detectClusters } from 'ngraph.leiden'\n\nconst g = createGraph()\n// Undirected graphs: just add a single link; adapter will symmetrize for you\ng.addNode('a'); g.addNode('b'); g.addNode('c'); g.addNode('d')\ng.addLink('a','b')\ng.addLink('c','d')\n\nconst result = detectClusters(g, { randomSeed: 42 })\n\n// Get a community id for a node\nconsole.log('a ->', result.getClass('a'))\n\n// Group membership as Map<communityId, nodeId[]>\nconsole.log(result.getCommunities())\n\n// Partition quality for the chosen objective\nconsole.log('Q =', result.quality())\n```\n\nCommonJS:\n\n```js\nconst createGraph = require('ngraph.graph')\nconst { detectClusters } = require('ngraph.leiden')\n```\n\n## API\n\nSignature\n- `detectClusters(input, options?) => Clusters`\n\nInput\n- `input`: either\n  - an `ngraph.graph` instance; or\n  - a multilayer array: `[{ graph, weight?, linkWeight?, nodeSize? }]` — all layers must share the same node ids (see Multilayer graphs).\n\nReturn value: `Clusters`\n- `getClass(nodeId): number` — community id for `nodeId`.\n- `getCommunities(): Map<number, string[]>` — nodes grouped by community id.\n- `quality(): number` — objective value for the final partition. With `quality: 'cpm'`, see CPM on how it’s computed and `options.cpmMode`.\n- `toJSON(): { membership: Record<id, number>, meta: { levels: number, quality: number, options: object } }`.\n\nOptions\n\nEach option below is optional. Defaults are shown in backticks.\n\n### quality\n- What: Objective to optimize.\n- Values: `'modularity'` | `'cpm'`. Default: `'modularity'`.\n- Why: Use `'modularity'` for classic community detection; use `'cpm'` (Constant Potts Model) when you need explicit control over community granularity via `resolution` or when modularity’s resolution limit is an issue.\n- When: Prefer `'cpm'` for very large graphs or when you want consistent small communities; otherwise `'modularity'` is a strong default.\n\n### resolution (CPM)\n- What: The `gamma` parameter for CPM.\n- Value: `number`. Default: `1.0`.\n- Why: Larger `resolution` yields more/smaller communities; smaller yields fewer/larger.\n- When: Tune to match desired granularity; try `0.1`, `1.0`, `5.0` as starting points.\n\n### directed\n- What: Enable Leicht–Newman directed modularity.\n- Value: `boolean`. Default: `false`.\n- Why: For directed networks where in/out strengths matter.\n- When: Set `true` for directed graphs. For undirected, keep `false` and add reciprocal links in your graph.\n\n### randomSeed\n- What: Seed for the internal RNG used for node order shuffles.\n- Value: `number`. Default: `42`.\n- Why: Ensures deterministic, reproducible partitions.\n- When: Set explicitly for reproducible experiments or tests.\n\n### candidateStrategy\n- What: Controls which target communities are considered when moving a node.\n- Values: `'neighbors'` (default), `'all'`, `'random'`, `'random-neighbor'`.\n- Why: Trade-off between speed and search breadth.\n- When:\n  - `'neighbors'`: fastest and typical; consider only adjacent communities.\n  - `'all'`: exhaustive but slow on large graphs.\n  - `'random'`: sample from all communities (broader search at bounded cost).\n  - `'random-neighbor'`: sample from neighbor communities (cheap, slightly more exploratory).\n\n### allowNewCommunity\n- What: Allow moves that create a fresh singleton community.\n- Value: `boolean`. Default: `false`.\n- Why: Can help escape local minima in specific structures.\n- When: Rarely needed; try enabling if you see over-merged communities.\n\n### maxCommunitySize\n- What: Upper bound on a community’s total size.\n- Value: `number`. Default: `Infinity`.\n- How measured: Uses `nodeSize` (default `1` per node). A move that would exceed this bound is skipped.\n- Why: Enforce capacity or balance constraints.\n- When: Useful for constrained clustering or to avoid giant communities.\n\n### refine\n- What: Enable Leiden-style refinement between coarsening levels.\n- Value: `boolean`. Default: `true`.\n- Why: Improves partitions by re-optimizing within coarse communities.\n- When: Keep `true` for best quality; turn off for speed-sensitive runs.\n\n### fixedNodes\n- What: Nodes that must remain in their initial communities at the finest level.\n- Value: `Set` or `Array` of node ids.\n- Why: Respect domain constraints or anchor communities.\n- When: Use to pin landmarks, seeds, or known group members.\n\n### preserveLabels\n- What: Control how community ids are compacted after renumbering.\n- Values: `false` (default), `true` (preserve old order), or `Map<oldId, order>`.\n- Why: Stable ids across runs or alignment to a predefined ordering.\n- When: Advanced; mostly for downstream integration/visualization.\n\n### linkWeight\n- What: Function to read an edge’s weight.\n- Signature: `(link) => number`. Default: `link.data?.weight ?? 1`.\n- Why: Use custom attributes (e.g., frequency, strength) as weights.\n- Example:\n  ```js\n  const res = detectClusters(g, { linkWeight: l => Math.max(0, l.data?.w ?? 0) })\n  ```\n\n### nodeSize\n- What: Function to read a node’s size (used by CPM and `maxCommunitySize`).\n- Signature: `(node) => number`. Default: `node.data?.size ?? 1`.\n- Why: Make CPM size-aware or weight capacity by node importance.\n- Example:\n  ```js\n  const res = detectClusters(g, { nodeSize: n => n.data?.pop ?? 1, quality: 'cpm' })\n  ```\n\n### maxLevels, maxLocalPasses\n- What: Internal performance knobs for the multi-level loop and local passes.\n- Values: `number`. Defaults are conservative and usually fine.\n- Why/When: Only tune if you profile and identify a need.\n\n## Vocabulary\n\n- Modularity: Measures how much more densely connected nodes are within communities than expected at random. Directed modularity (Leicht–Newman) uses in/out strengths. Higher is better; can suffer from a resolution limit on very large graphs.\n- CPM (Constant Potts Model): Maximizes internal edge weight minus gamma × a penalty for community size. Gamma (resolution) controls granularity: larger gamma → more/smaller communities; smaller gamma → fewer/larger. Supports custom node sizes via nodeSize.\n\n## CPM\n\nCPM is a resolution-tunable objective. During optimization this package uses node sizes (via nodeSize), so gains reflect community size; with default nodeSize=1 this matches “unit-count” CPM. If you supply custom node sizes, the optimization becomes size-aware. The quality() reporter supports:\n\n- options.cpmMode: 'unit' | 'size-aware' (affects only how quality() is computed, not the move heuristic). If you use custom node sizes and want \"unit-count\" reporting, keep cpmMode='unit'.\n\n## Multilayer graphs\n\nPass an array of layers: [{ graph, weight?, linkWeight?, nodeSize? }]. Edges are aggregated by summing weight * linkWeight(link) per layer. All layers must have the same set of node ids. Node sizes default to the first layer’s nodeSize.\n\nExample:\n\n```js\nconst result = detectClusters([\n  { graph: layer1, weight: 1.0 },\n  { graph: layer2, weight: 0.2 },\n], { quality: 'modularity', randomSeed: 7 })\n```\n\nWhen to use it\n- Multiplex networks: combine different relation types (e.g., friendship + collaboration).\n- Temporal smoothing: blend snapshots with weights to reduce short-term noise.\n- Heterogeneous signals: fuse a strong–sparse layer with a weak–dense layer.\n- Denoising: add a lightly weighted prior layer to stabilize communities.\n\n## Directed graphs\n\nSet { directed: true } to use Leicht–Newman directed modularity. Edges are taken as-is; no reciprocal links are needed.\n\nUndirected handling\n- If directed: false (default), the adapter symmetrizes edges so you don’t need to add reciprocal links to your ngraph.graph.\n- If both directions exist between two nodes with possibly different weights, the adapter averages them: w_undirected = (w_ij + w_ji) / 2, then emits symmetric edges with that weight. This preserves total weight and keeps results consistent whether you supplied one or both directions.\n\n## Constraints and ergonomics\n\n- Fixed nodes: keep given nodes in their initial communities at the finest level (also respected during refinement).\n- Community size limit: maxCommunitySize prevents moves that would exceed the given total nodeSize.\n- Determinism: randomSeed controls shuffle order; repeated runs with the same seed and inputs are deterministic.\n- Negative weights and self-loops are supported; use negative weights with care as modularity assumptions may not hold theoretically.\n\n## Examples\n\nModularity with custom weights\n\n```js\nconst g = createGraph()\ng.addNode('x'); g.addNode('y'); g.addNode('z')\ng.addLink('x','y', { weight: 2 }); g.addLink('y','x', { weight: 2 })\ng.addLink('y','z', { weight: 0.3 }); g.addLink('z','y', { weight: 0.3 })\n\nconst res = detectClusters(g, { quality: 'modularity', randomSeed: 1, linkWeight: l => l.data?.weight ?? 1 })\n```\n\nCPM with resolution and node sizes\n\n```js\nconst res = detectClusters(g, {\n  quality: 'cpm',\n  resolution: 0.5,\n  nodeSize: n => n.data?.size ?? 1,\n  randomSeed: 3,\n})\n```\n\nFix a subset of nodes\n\n```js\nconst res = detectClusters(g, { fixedNodes: new Set(['x','z']), randomSeed: 11, refine: true })\n```\n\n## Build and test\n\n- Build library bundles: `npm run build`\n- Run tests: `npm test`\n\n## CLI\n\nThis package ships a small CLI for quick community detection (via npx or installed locally).\n\nInput format is auto-detected by file extension (.dot/.gv/.json) or by content (tries JSON first, then DOT). Use --format to override.\n\nUsage examples\n\n- From a DOT file\n\n```sh\nnpx ngraph.leiden --in graph.dot --out membership.json\n```\n\n- From stdin\n\n```sh\ncat graph.dot | npx ngraph.leiden --membership-only\n```\n\n- From a JSON edgelist (either an array of {source,target,weight?} or {nodes,links})\n\n```sh\ncat edges.json | npx ngraph.leiden > out.json\n```\n\nOptions\n\n- `--directed` — treat input as directed\n- `--quality` modularity|cpm (default modularity)\n- `--resolution <gamma>` — CPM resolution parameter\n- `--candidate-strategy` neighbors|all|random|random-neighbor\n- `--max-levels`, `--max-local-passes`, `--random-seed`\n- `--max-community-size <num>`\n- `--allow-new-community`, `--no-refine`\n- `--fixed <file>` — newline-separated node ids to keep fixed at level 0\n- `--membership-only` — print only the id->community map\n\nOutput\n\n- Defaults to JSON on stdout; use `--out <file>` to write to a file.\n- Formats:\n  - JSON (default): full object `{membership, meta}` or mapping only with `--membership-only`.\n  - CSV: `--out-format csv` prints header `nodeId,communityId`.\n  - DOT: `--out-format dot` overlays `community=\"...\"` on nodes using ngraph.todot.\n\nQuality-only evaluation\n\nEvaluate modularity/CPM for an existing membership mapping without running detection:\n\n```sh\nnpx ngraph.leiden \\\n  --in graph.dot --format dot \\\n  --evaluate --membership membership.json \\\n  --quality modularity\n```\n\n## License\n\nMIT © Andrei Kashcha\n","readmeFilename":"README.md"}