Source-linked AI summary
Directed network modules
Gergely Palla, Illes J. Farkas, Peter Pollner, Imre Derenyi, Tamas Vicsek
TL;DR
The paper addresses how to identify internally dense, overlapping modules in directed networks when link direction carries structural meaning. It extends Clique Percolation Method with directed k-cliques, studies the resulting percolation transition analytically and numerically, and applies the method to four real-world networks. The real-world modules overlap, with word-association and Google networks tending toward in-hub overlaps and email and yeast regulatory networks toward out-hub overlaps.
Problem
Existing module-finding methods often ignore link direction, although incoming- and outgoing-dominated nodes can have different roles within networks and modules.
Method
The paper defines directed k-cliques and a directed Clique Percolation Method, then analyzes Erdős-Rényi percolation and applies CPMd to four real-world directed networks.
Results
Directed modules in the studied real-world networks inherently overlap, with overlaps likely containing in-hubs in word-association and Google networks and out-hubs in email and yeast regulatory networks.
Takeaways & Limitations
Directed module analysis can distinguish networks by whether their overlapping modules tend to connect through in-hubs or out-hubs.
Takeaways & Limitations
The directed k-clique definition is one deliberately restrictive choice among several possible definitions, and the percolation derivation neglects continuation through double edges at leading order.
Abstract
from arXiv · showhide
A search technique locating network modules, i.e., internally densely connected groups of nodes in directed networks is introduced by extending the Clique Percolation Method originally proposed for undirected networks. After giving a suitable definition for directed modules we investigate their percolation transition in the Erdos-Renyi graph both analytically and numerically. We also analyse four real-world directed networks, including Google's own webpages, an email network, a word association graph and the transcriptional regulatory network of the yeast Saccharomyces cerevisiae. The obtained directed modules are validated by additional information available for the nodes. We find that directed modules of real-world graphs inherently overlap and the investigated networks can be classified into two major groups in terms of the overlaps between the modules. Accordingly, in the word-association network and among Google's webpages the overlaps are likely to contain in-hubs, whereas the modules in the email and transcriptional regulatory networks tend to overlap via out-hubs.
1. Introduction
The paper extends network-module analysis to directed networks, motivated by the need to identify overlapping, densely connected groups while preserving link direction. It introduces directed k-cliques and CPMd, then applies them to random and real-world networks.
- Network modules are intermediate-scale groups whose nodes connect more densely to one another than to the rest of the network.
- Reliable module methods should be local, link-density based, error-tolerant, and able to represent overlaps between groups.
- CPM defines modules as unions of k-cliques connected through a chain of adjacent cliques sharing k −1 nodes.
- Existing module methods commonly ignore link direction, although incoming- and outgoing-dominated nodes can play different network roles.
- The paper defines directed k-cliques, proposes CPMd, analyzes Erdős-Rényi percolation, and studies four directed real-world networks with external node information for validation.
2. Definitions
The paper characterizes directed modules through node roles and replaces ordinary cliques with ordered directed k-cliques. CPMd then links these directed cliques when they share k −1 nodes.
- Directed networks allow single links in either direction or double links between a node pair, unlike undirected graphs.
- Comparing nodes: Relative in-degree and out-degree compare each node’s incoming and outgoing links to other members of its module.These values use within-module neighbors; weighted networks can analogously use relative strengths.
- Directed k-cliques: A directed k-clique is a complete k-node subgraph orderable so every directed link points from higher order to lower order.
- Directed k-cliques: For cliques without double links, valid ordering requires no directed loops and distinct restricted out-degrees, with links directed toward lower-order nodes.
- Directed k-cliques: Directed cliques preserve an overall source-to-drain direction, with the highest-order node acting as a source and the lowest-order node as a drain.
YES NO
The paper illustrates which complete directed subgraphs qualify as directed k-cliques and defines CPMd modules by percolating through adjacent directed cliques. Its chosen definition is deliberately restrictive but is only one possible directed-clique criterion.
- A directed k-clique has an ordering that produces a coherent direction from higher-order nodes toward lower-order nodes.
- Complete subgraphs fail when directed loops remain, including cases where double links cannot be resolved into a loop-free ordering.
- CPMd modules are unions of directed k-cliques connected through adjacency defined by sharing k −1 nodes.
- The directed k-clique definition is one restrictive choice among several possible ways to impose directionality on cliques.The authors motivate it partly because it provides a specific tool for studying directionality and resembles undirected modules in most real-world networks.
3. Percolation transition in the directed ER graph
The directed Erdős–Rényi graph exhibits a percolation transition for directed k-clique clusters, analyzed through branching arguments and finite-size simulations. Numerical results support the theoretical critical point and show distinct behavior for node- and clique-based order parameters.
- The directed Erdős–Rényi graph places each of N(N−1) possible directed links independently with probability p, yielding M ≃ N(N−1)p edges on average.
- The critical probability is estimated by requiring one unexplored adjacent directed k-clique on average during the branching exploration.This criterion allows the directed k-clique template to continue rolling at criticality.
- Directed k-clique exploration has k−1 relocation choices, approximately N possible destinations, and direction constraints that reduce the allowed link configurations.The directed-clique conditions determine the effective branching factor used for the theoretical threshold.
- For k = 2, the critical directed-edge probability obeys the p_c/2 relation, consistent with twice as many possible directed as undirected links.
- The largest cluster can be measured by its number of nodes, N*, or by its number of directed k-cliques, N*; their relative order parameters are Φ and Ψ, respectively.The node-based and clique-based measures capture complementary aspects of the largest percolation cluster.
- For k = 4 and N = 50–1600, Φ approaches a step function while Ψ grows continuously above p/p_c(k) = 1; susceptibility peaks at the numerical transition.Finite-size scaling shows p_c^num/p_c converging to one approximately as 1 + cN^-1/2 for large systems.
4. Results for real-world graphs
CPMd analyzes directed modules across four real-world networks, with parameters tuned near the percolation transition and module structure validated through node information. The networks separate into in-hub-overlapping and out-hub-overlapping groups, while CPMd largely preserves modules found by undirected CPM.
- Method: CPMd uses clique size k and, for weighted networks, threshold w∗ to control the resolution of directed-module analysis.For whole-network analysis, parameters are tuned just below the percolation threshold to find many modules without merging them into a giant module.
- Word association graph: The word association network contains four strongly internally connected modules for the different meanings of “GOLD” at k = 4 and w∗= 0.023.Higher relative out-strength corresponds to less frequently used words, whereas common words tend to have lower relative out-strength.
- Google’s web-pages: Google’s modules share in-hubs but not out-hubs, and overlapping cores support movement between topics and efficient hierarchical browsing.The analyzed collection contained 15,763 pages and 171,206 directed links before additional analysis restrictions.
- Email network: Email modules share out-hubs: nodes with the highest module membership have significantly more outgoing than incoming links.The analysis compares internal-only emails with the full network containing internal and external messages.
- Transcriptional regulatory network: Yeast transcriptional modules are organized around major transcription-factor out-hubs, with overlaps occurring through regulators or groups of target genes.The yeast network is therefore organized similarly to the email network and oppositely to Google’s web-pages and the word association network.
- Comparison between CPMd and CPM: About 70% of modules coincide between CPMd and CPM for the word association and Google networks, versus around 90% for email and yeast transcriptional networks.The authors report that the remaining directed modules usually have relatively similar undirected counterparts, indicating robustness of the original CPM.
- Classification of real-world networks: The four real-world networks divide into two groups: word association and Google overlap through in-hubs, whereas email and yeast more often overlap through out-hubs.The comparison uses average module membership as a function of relative out-degree.
5. Summary and conclusions
The paper extends clique percolation to directed networks by defining directed modules, analyzing their ER percolation transition, and studying four real-world networks. It validates the modules with node annotations and classifies networks by how their modules overlap.
- The study introduces directed network modules and a corresponding directed module-finding algorithm based on k-clique percolation.
- The directed k-clique percolation threshold in the ER graph is derived analytically and supported by numerical simulations.
- Four real-world directed networks are analyzed, and their modules are validated using additional information about their nodes.
- Overlapping nodes classify the examined networks into two groups based on whether overlaps involve in-hubs or out-hubs.
Appendix A
This appendix establishes equivalent structural properties for directed k-cliques without double links. The equivalence connects link orientation, absence of directed loops, and distinct restricted out-degrees.
- A directed k-clique satisfies three equivalent conditions when it has no double links.
- Every link points from a node with higher restricted out-degree to one with lower restricted out-degree.
- The k-clique contains no directed loops, and each node has a different restricted out-degree within the clique.
- Restricted out-degree is the number of a node’s out-neighbours among the other members of the k-clique.
- With double links, the conditions cannot hold because the additional links make the total link count exceed k(k −1)/2 and force repeated restricted out-degrees.
Appendix B
The appendix describes extracting directed CPM modules by finding maximal directed cliques and connecting them through sufficiently large overlaps. It also outlines a back-tracing search and notes both computational efficiency in practice and non-polynomial worst-case extraction.
- A directed clique is a maximal directed k-clique, and a CPMd module is the union of directed cliques connected through overlaps of at least k −1 nodes.
- The extraction procedure repeatedly finds all directed cliques associated with a node, then removes that node and its links from the network.
- The back-tracing search maintains containers for in-neighbours and out-neighbours and places selected nodes into a hierarchy consistent with directed-clique ordering.
- Directed-clique extraction is non-polynomial because finding the full set of graph cliques is widely believed to be non-polynomial.
- A complete analysis of the word-association network with over 70,000 links takes less than 5 minutes on a PC.