Saturday, November 21, 2026
Science
No Result
View All Result
  • Login
  • HOME
  • SCIENCE NEWS
  • CONTACT US
  • HOME
  • SCIENCE NEWS
  • CONTACT US
No Result
View All Result
Scienmag
No Result
View All Result
Home Science News Technology and Engineering

New algorithm counts the hidden building blocks of multilayer networks

November 6, 2026
in Technology and Engineering
Denise Maddox
By Denise Maddox Scienmag Editorial Profile - Mechanical Engineering
Reading Time: 6 mins read
0
New algorithm counts the hidden building blocks of multilayer networks

New algorithm counts the hidden building blocks of multilayer networks

65
SHARES
587
VIEWS
Share on FacebookShare on Twitter
ADVERTISEMENT

Networks are rarely as simple as a single web of connections. A city’s commuters ride metro lines, trains and buses; students relate to each other as friends, classmates or online contacts; a worm’s neurons communicate through several distinct kinds of links. Scientists represent such systems as multilayer networks, and among the most widely used special cases are multiplex networks, in which the same set of nodes exists in every layer. A new study published in Applied Network Science introduces MPCount, a computational tool that counts, exactly and efficiently, all the small subgraphs of a specified size in multiplex networks, filling a gap that researchers say has limited the practical analysis of these systems.

Subgraphs are the small structural pieces of a network: triangles, stars, chains and other configurations of a handful of nodes and edges. Counting how often each type appears, a task known as a subgraph census, is a core operation in network science because it underpins higher-level analyses such as the detection of statistically overrepresented subgraphs called motifs and the computation of graphlet degree signatures. Yet the task is computationally hard. It is directly related to the subgraph isomorphism problem, which is NP-complete for general graphs, so researchers are often restricted to small subgraphs or to specific predefined structures. The authors of the new work, André Couto Meira and Pedro Ribeiro, note that no general polynomial-time solution is known, which drives the search for efficient methodologies.

While single-layer networks have been studied for decades, multilayer network analysis has gained momentum only in recent years, supported by foundational formalisms that established a coherent theoretical framework and by some general software tools. The authors argue that the practical side of multilayer analysis still remains relatively underdeveloped, limiting the ability to fully explore these systems and potentially leaving important phenomena undiscovered. For the multilayer case, the existing literature on subgraph counting is limited, and the few available approaches are often difficult to apply or computationally inefficient. Some existing methods work only for very specific subgraph types, such as three-node subgraphs, three-edge subgraphs or triangles; others are limited to two layers, use frequency concepts that do not allow overlapping edges between occurrences, or focus on graphlets and the structural position of nodes inside multiplex subgraphs.

Multiplex networks add a specific twist to the counting problem. Because subgraphs may span multiple layers, researchers must decide when two subgraphs count as the same structure. The new work distinguishes two notions of multiplex isomorphism. Node isomorphism requires a bijection between the nodes that preserves the exact same connections in each layer. Node-layer isomorphism additionally allows a bijection between the layers themselves, so that structures differing only by an exchange of layer labels are treated as equivalent. The authors illustrate the difference with triangles in a three-layer example network: under node isomorphism there are three types of triangles, while under node-layer isomorphism two of those types merge into one because the red and yellow layers can be mapped onto each other. In a real application, one concept might be more suitable than the other, and MPCount supports both.

The new method builds on well-established machinery from single-layer network analysis. The ESU algorithm, designed to eliminate symmetry redundancy, enumerates each subgraph exactly once by selecting a starting node and recursively expanding partial subgraphs through a maintained list of candidate nodes. Later algorithms such as FaSE preserved this non-redundant enumeration strategy but substantially improved the efficiency of isomorphism testing by grouping subgraphs according to their shared topological structure and executing a single isomorphism test per group. FaSE takes advantage of a specialized data structure called a g-trie, analogous to a prefix tree used for organizing words by common prefixes, which organizes graphs by their shared substructures and yields significant savings in both memory and execution time.

MPCount adapts this machinery to the multiplex setting. The tool takes as input a multiplex network, represented as an edge list, and a subgraph size k. During reading of the network it constructs an auxiliary overlap matrix that records whether there is any connection between two nodes across all layers, with each element true only if at least one edge connects the nodes in any layer. This aggregation is not a computation time bottleneck, since it can be done during edge reading, and in terms of memory it is the same as containing a new layer. The overlap network then allows the use of efficient enumeration algorithms originally designed for monoplex networks, particularly an adapted version of ESU enhanced with ideas from FaSE, which guarantees that each subgraph is enumerated exactly once.

During enumeration, each time a new node is added to a subgraph, a label is generated to encode its connections in all layers, multiplying the monoplex process by the number of layers. These labels are stored in a g-trie, allowing repeated patterns to be aggregated and avoiding redundant computations in subsequent steps. The leaf nodes of the g-trie store the frequencies of each subgraph type, with many occurrences producing the same tree path and ending on the same leaf. Different leaf nodes may still correspond to the same isomorphic class, so the tool relies on the external isomorphism detection program nauty to obtain each class. The authors emphasize that heuristic approximations such as the Weisfeiler-Leman test are not adequate for their purposes, because unlike that test, which is designed to quickly and approximately distinguish non-isomorphic graphs without guaranteeing correctness, their task requires grouping topologies into exact isomorphic classes.

To reduce the multiplex isomorphism problem to a classical one, the method reconstructs each subgraph representation into a supra-adjacency matrix, which encodes all layer connections and preserves the structural properties of the subgraph. Supernodes, which remain consistent across all subgraphs, are systematically added to the matrix, and nauty computes canonical orderings of the nodes so that two subgraphs are isomorphic if and only if they share the same canonical representation. Crucially, a matrix is created for each g-trie leaf rather than for each individual subgraph, drastically reducing the number of isomorphism checks and speeding up the process. The final output is a complete census of subgraphs of a given size, grouped by isomorphic class along with their frequencies, complemented with visualization resources that present the results as Scalable Vector Graphics in HTML pages, with edges split into colored segments representing connections in different layers.

The experimental comparison faced a sparse field: the authors report that they found only two available implementations that could be directly compared, an adaptation of the SubEnum algorithm by Takes and colleagues, developed for finding motifs in multiplex corporate networks, and the pymnet library, which supports both types of multiplex isomorphism but relies on a more general multilayer enumeration approach. Experiments were conducted on a machine equipped with an Intel Core i7-4710HQ CPU, using a C++ implementation of MPCount that the authors make available online. The datasets combined synthetic networks randomly generated through the Erdős–Rényi model, with varying numbers of layers and nodes, and four real-world multiplex networks obtained from Manlio De Domenico’s website: VickChan, representing seventh grade students and different types of personal relationships; CSAarhus, consisting of five kinds of online and offline relationships between employees of a Computer Science department; CElegans, the connectome of the C. Elegans organism with layers of different types of neural connections; and AirLines, whose layers correspond to different airlines operating in Europe, of which the first 7 of the original 37 layers were used so the experiments could run in a reasonable amount of time.

Against pymnet, tested on undirected networks for subgraph sizes of 3, 4 and 5 nodes with a 24-hour cutoff, MPCount was always faster, by 3 to 5 orders of magnitude, while both methods found the same numbers of subgraph occurrences and isomorphic classes. Against the adapted SubEnum, MPCount was at least twice as fast at every tested scale. The comparison also surfaced a correctness problem in the competing tool: depending on the number of layers, the adapted SubEnum found the same number of occurrences but a different number of isomorphic classes, and testing on small hand-checkable networks led the authors to conclude that it was unable to identify the isomorphic classes correctly for networks with more than 6 layers, demonstrated on the AirLines network. The issue lies in the modification whereby each binary edge label was replaced with a numeric digit label using a single character, which is insufficient to encode a large number of layers; the authors note that the adaptation was developed with a three-layer scenario in mind, in which it calculates accurately. For synthetic networks, where the Erdős–Rényi model generates random networks independently in each layer and produces higher subgraph occurrences than most real networks, the tests identified subgraphs in the tens of millions and confirmed a consistent number of subgraphs processed per second, suggesting performance largely independent of network characteristics. The authors plan to extend the work to the more general multilayer case, reduce the memory footprint by exploiting matrix sparsity, and pursue parallelism and sampling to trade accuracy for speed on larger networks.

Subject of Research: An exact subgraph counting algorithm for multiplex networks

Article Title: Counting subgraphs in multiplex networks

Article References: Meira, A. C., & Ribeiro, P. (2026). Counting subgraphs in multiplex networks. Applied Network Science, 11(1), Article 58. https://doi.org/10.1007/s41109-026-00812-4

Image Credits: AI Generated

DOI: 10.1007/s41109-026-00812-4

Keywords: multiplex networks, multilayer networks, subgraph census, network motifs, graph mining, isomorphism, g-trie, nauty, Applied Network Science, computational complexity, network science, algorithm

Cite Scienmag News

Denise Maddox. (November 6, 2026). New algorithm counts the hidden building blocks of multilayer networks. Scienmag. https://scienmag.com/new-algorithm-counts-the-hidden-building-blocks-of-multilayer-networks/

Denise Maddox. "New algorithm counts the hidden building blocks of multilayer networks." Scienmag, 6 November 2026, https://scienmag.com/new-algorithm-counts-the-hidden-building-blocks-of-multilayer-networks/. Accessed 21 November 2026.

Denise Maddox. "New algorithm counts the hidden building blocks of multilayer networks." Scienmag. November 6, 2026. https://scienmag.com/new-algorithm-counts-the-hidden-building-blocks-of-multilayer-networks/

Tags: algorithmApplied Network Sciencecomputational complexityg-triegraph miningisomorphismmultilayer networksmultiplex networksnautynetwork motifsnetwork sciencesubgraph census
Share26Tweet16
Previous Post

New Forest Edges Facing West Nearly Quadruple Wind Damage Odds in Swedish Forests

Next Post

Personalized exoskeleton gait patterns fail to beat standard ones in comfort trial

Related Posts

Portable Raman Spectroscopy Screens Microbial Carotenoids for Solar Cell Fabrication
Technology and Engineering

Portable Raman Spectroscopy Screens Microbial Carotenoids for Solar Cell Fabrication

November 21, 2026
New Unified Contraction Framework Establishes Fixed Point Results in Metric Spaces
Technology and Engineering

New Unified Contraction Framework Establishes Fixed Point Results in Metric Spaces

November 21, 2026
Simulations Show Zwitterion Pair Enhances Dialysis Membrane Blood Compatibility
Technology and Engineering

Simulations Show Zwitterion Pair Enhances Dialysis Membrane Blood Compatibility

November 21, 2026
Electrospun Polymer-Derived Carbon Fibers Deliver Effective Lightweight Electromagnetic Shielding
Technology and Engineering

Electrospun Polymer-Derived Carbon Fibers Deliver Effective Lightweight Electromagnetic Shielding

November 21, 2026
Digital Twin Framework Coordinates Vehicular Edge Computing with Opportunistic Vehicles
Technology and Engineering

Digital Twin Framework Coordinates Vehicular Edge Computing with Opportunistic Vehicles

November 21, 2026
Machine Learning and In-Line Sensors Accurately Predict Extruded Drug Delivery Properties
Technology and Engineering

Machine Learning and In-Line Sensors Accurately Predict Extruded Drug Delivery Properties

November 21, 2026
Next Post
Personalized exoskeleton gait patterns fail to beat standard ones in comfort trial

Personalized exoskeleton gait patterns fail to beat standard ones in comfort trial

  • Mothers who receive childcare support from maternal grandparents show more optimized

    Mothers who receive childcare support from maternal grandparents show more parental warmth, finds NTU Singapore study

    27656 shares
    Share 11059 Tweet 6912
  • University of Seville Breaks 120-Year-Old Mystery, Revises a Key Einstein Concept

    1061 shares
    Share 424 Tweet 265
  • Bee body mass, pathogens and local climate influence heat tolerance

    682 shares
    Share 273 Tweet 171
  • Researchers record first-ever images and data of a shark experiencing a boat strike

    546 shares
    Share 218 Tweet 137
  • Groundbreaking Clinical Trial Reveals Lubiprostone Enhances Kidney Function

    531 shares
    Share 212 Tweet 133
Science

Embark on a thrilling journey of discovery with Scienmag.com—your ultimate source for cutting-edge breakthroughs. Immerse yourself in a world where curiosity knows no limits and tomorrow’s possibilities become today’s reality!

RECENT NEWS

  • Pediatric Radiology Surveys Reveal Gaps in Institutional Support for Fertility Preservation
  • Magnetic Fields Suppress Vibrations to Improve Titanium Alloy Diamond Machining Precision
  • Portable Raman Spectroscopy Screens Microbial Carotenoids for Solar Cell Fabrication
  • Diabetes Risk Reverses Between Chinese Men and Women Around Age Fifty

Categories

  • Agriculture
  • Anthropology
  • Archaeology
  • Athmospheric
  • Biology
  • Biotechnology
  • Blog
  • Bussines
  • Cancer
  • Chemistry
  • Climate
  • Earth Science
  • Editorial Policy
  • Marine
  • Mathematics
  • Medicine
  • Pediatry
  • Policy
  • Psychology & Psychiatry
  • Science Education
  • Science News
  • Social Science
  • Space
  • Technology and Engineering

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 5,151 other subscribers

© 2026 Scienmag - Science Magazine

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
No Result
View All Result
  • HOME
  • SCIENCE NEWS
  • CONTACT US

© 2026 Scienmag - Science Magazine

Discover more from Science

Subscribe now to keep reading and get access to the full archive.

Continue reading