Scalable algorithms for multiple network alignment
From MaRDI portal
\(K\)-dimensional matching\(K\)-partite matchinglow-rank tensormultiple network alignmentnetwork alignment
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Deterministic network models in operations research (90B10)
Abstract: Multiple network alignment is the problem of identifying similar and related regions in a given set of networks. While there are a large number of effective techniques for pairwise problems with two networks that scale in terms of edges, these cannot be readily extended to align multiple networks as the computational complexity will tend to grow exponentially with the number of networks.In this paper we introduce a new multiple network alignment algorithm and framework that is effective at aligning thousands of networks with thousands of nodes. The key enabling technique of our algorithm is identifying an exact and easy to compute low-rank tensor structure inside of a principled heuristic procedure for pairwise network alignment called IsoRank. This can be combined with a new algorithm for -dimensional matching problems on low-rank tensors to produce the alignment. We demonstrate results on synthetic and real-world problems that show our technique (i) is as good or better in terms of quality as existing methods, when they work on small problems, while running considerably faster and (ii) is able to scale to aligning a number of networks unreachable by current methods. We show in this paper that our method is the realistic choice for aligning multiple networks when no prior information is present.
Recommendations
Cites work
- A Survey on PageRank Computing
- Approximation Algorithms for Some Graph Partitioning Problems
- Bounded-rank tensors are defined in bounded degree
- Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
- Fast Katz and commuters: efficient estimation of social relatedness in large networks
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Lagrangian relaxations for multiple network alignment
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- PageRank beyond the web
- Reducibility among combinatorial problems
- The complexity of theorem-proving procedures
- Two New Inequalities
Cited in
(9)- Natalie 2.0: sparse global network alignment as a special case of quadratic assignment
- Lagrangian relaxations for multiple network alignment
- Credible seed identification for large-scale structural network alignment
- Multiple Alignment, Communication Cost, and Graph Matching
- Multiple network alignment on quantum computers
- ELRUNA: elimination rule-based network alignment
- Maximum common subgraph based social network alignment method
- scientific article; zbMATH DE number 6304438 (Why is no real title available?)
- Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple
This page was built for publication: Scalable algorithms for multiple network alignment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009904)
