Introduction

A hypergraph is a generalization of a graph in which an edge can connect any number of nodes. Formally, a hypergraph is a tuple (V;E) where V is the set of nodes and E is a set of nonempty subsets of V called hyperedges. Graphs are a special case of hypergraphs in which each hyperedge connects exactly two nodes. Figure 1 shows an example of a hypergraph. Hyperedges can be represented as communities in our problem.

Hypergraphs arise naturally in many application domains. In biology, protein protein interaction network can be modeled as hyprgraphs where proteins are nodes in the hypergraph and interactions can be modeled as hyperedges [1]. In VLSI design, circuits are often modeled as hypergraphs; nodes in the hypergraph represent the pins of the circuit and hyperedges represent wires from the output pin of a gate to the input pins of other gates [2]. In Boolean satisfiability, a Boolean formula can be represented as a hypergraph in which nodes represent clauses and hyperedges represent the occurrences of a given literal in these clauses.

In many of these applications, it is necessary to create a given number of partitions of the hypergraph. The goal of hypergraph partitioning is to create a given number of partitions of the nodes of the hypergraph such that (1) the partitions are balanced, within a given margin, for some balance criterion such as the number of nodes in each partition, and (2) the number of cut hyperedges, i.e., hyperedges that span multiple partitions, is minimized. In some applications, hyperedges have weights, and it is required to minimize the sum of the weights of the cut hyperedges while achieving balance.

The problem we are studying is that, given a network of protein protein interaction, find communities of proteins that interact with each other. The stated problem is a generalization of hypergraph partitioning. In this scenario, the goal is to find hyperedges (communities) given the pair interaction between proteins.

This project makes the following contributions.

• Introduce a weight aware hypergraph partitioner

• Explore the potential communities in Saccharomyces cerevisiae protein-protein interaction network

• A systematic evaluation of detected communities