Bruno Coutinho (Instituto de Telecomunicações)
Abstract:
A hypergraph is a natural generalization of a graph, where an edge (often called hyperedge) can simultaneously connect any number of vertices. The fact that hyperedges can connect more than two vertices facilitates a more faithful representation of many real-world networks. For example, given a set of proteins and a set of protein complexes, the corresponding hypergraph naturally captures the information on proteins that interact together within a protein complex. For a biochemical reaction system, the hypergraph representation indicates which biomolecules participate in a particular reaction. Collaboration networks can also be represented by a hypergraph, where vertices represent individuals and hyperedges connect individuals who were involved in a specific collaboration, e.g. a scientific paper, a patent, a consulting task, or an art performance.
The core of a graph - defined as the remainder of the greedy leaf removal procedure where leaves (vertices of degree one) and their neighbors are removed iteratively from the graph - has been related to the conductor-insulator transition, structural controllability, and many combinatorial optimization problems. In fact, the size of the core is related to a fundamental combinatorial issue: the computational complexity of the minimum vertex cover (MVC) problem. The MVC aims to find the smallest set of vertices in a graph (or hypergraph) so that every edge (or hyperedge) is incident to at least one node in the set.
I will talk about two generalizations of the core in graphs to hypergraphs, one associated with the edge-cover problem and another associated with the vertex-cover problem. We found that these two cores tend to be very small in real-world hypergraphs. This result indicates that the hyperedge and vertex cover problems in real-world hypergraphs can actually be solved in polynomial time.
* * * * *
Date & time: 21/10/2016 at 16:00.
Location: Room P3.10, Mathematics Building, Instituto Superior Técnico, Lisbon.
Abstract:
A hypergraph is a natural generalization of a graph, where an edge (often called hyperedge) can simultaneously connect any number of vertices. The fact that hyperedges can connect more than two vertices facilitates a more faithful representation of many real-world networks. For example, given a set of proteins and a set of protein complexes, the corresponding hypergraph naturally captures the information on proteins that interact together within a protein complex. For a biochemical reaction system, the hypergraph representation indicates which biomolecules participate in a particular reaction. Collaboration networks can also be represented by a hypergraph, where vertices represent individuals and hyperedges connect individuals who were involved in a specific collaboration, e.g. a scientific paper, a patent, a consulting task, or an art performance.
The core of a graph - defined as the remainder of the greedy leaf removal procedure where leaves (vertices of degree one) and their neighbors are removed iteratively from the graph - has been related to the conductor-insulator transition, structural controllability, and many combinatorial optimization problems. In fact, the size of the core is related to a fundamental combinatorial issue: the computational complexity of the minimum vertex cover (MVC) problem. The MVC aims to find the smallest set of vertices in a graph (or hypergraph) so that every edge (or hyperedge) is incident to at least one node in the set.
I will talk about two generalizations of the core in graphs to hypergraphs, one associated with the edge-cover problem and another associated with the vertex-cover problem. We found that these two cores tend to be very small in real-world hypergraphs. This result indicates that the hyperedge and vertex cover problems in real-world hypergraphs can actually be solved in polynomial time.
* * * * *
Date & time: 21/10/2016 at 16:00.
Location: Room P3.10, Mathematics Building, Instituto Superior Técnico, Lisbon.
RSS Feed