Advances in Graph Theory and Network Analysis

The field of graph theory and network analysis is witnessing significant developments, with a focus on improving the efficiency and accuracy of algorithms for various applications. Researchers are exploring new approaches to tackle complex problems, such as graph decomposition, node embedding, and link prediction. Notably, there is a growing interest in incorporating attributes and weights into graph models to better capture real-world relationships. Furthermore, the development of new algorithms and techniques, such as sparse self-representation learning and spectral sparsification, is enabling the analysis of large-scale networks and graphs. Overall, these advancements are paving the way for breakthroughs in various domains, including social network analysis, recommendation systems, and supply chain management. Noteworthy papers include: The paper on A Structural Linear-Time Algorithm for Computing the Tutte Decomposition presents a conceptually simple algorithm for computing the Tutte-decomposition in linear time. The paper on The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem introduces a new variant of the Densest $k$-Subgraph problem that incorporates attribute values of vertices and proposes an efficient algorithm for solving it.

Sources

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition

The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem

A Joint Sparse Self-Representation Learning Method for Multiview Clustering

Recovering link-weight structure in complex networks with weight-aware random walks

Simple Algorithms for Fully Dynamic Edge Connectivity

C-MAG: Cascade Multimodal Attributed Graphs for Supply Chain Link Prediction

Sparsifying Sums of Positive Semidefinite Matrices

Effective and Efficient Attributed Hypergraph Embedding on Nodes and Hyperedges

An improved local search based algorithm for $k^-$-star partition

Efficient Integration of Multi-View Attributed Graphs for Clustering and Embedding

Simpler and Faster Contiguous Art Gallery

Built with on top of