# CS
6824: *Hypergraph Algorithms and Applications*

## T. M. Murali

### Spring 2014, 4:00pm-5:15pm, Mondays and Wednesdays, Randolph 320

Date | Topic and papers | Presenter(s) (links point to the presentations) |
---|---|---|

Wed, Jan 22, 2014 | Introduction to Hypergraphs | T. M. Murali |

Mon, Jan 27, 2014 | Short presentations on hypergraph-related papers | All students |

Wed, Jan 29, 2014 | Short presentations on hypergraph-related papers (contd.) | All students, same presentation as the previous class |

Mon, Feb 3, 2014 | Review of graph algorithms (shortest paths, spanning trees) | T. M. Murali |

Wed, Feb 5, 2014 | Review of graph algorithms (spanning trees, Steiner trees) | T. M. Murali, same lecture as the previous class |

Mon, Feb 10, 2014 | Review of graph algorithms (Steiner trees continued) | T. M. Murali, same lecture as the previous class |

Wed, Feb 12, 2014 | Class cancelled by university | |

Mon, Feb 17, 2014 | Course Papers and Projects | T. M. Murali |

Wed, Feb 19, 2014 | Class cancelled | |

Mon, Feb 24, 2014 | Class cancelled | |

Wed, Feb 26, 2014 | Review of graph algorithms (Flows and cuts) | T. M. Murali |

Mon, Mar 3, 2014 | Review of graph algorithms (Flows and cuts) Signaling Hypergraphs: A New Representation for Biological Signaling Pathways |
T. M. Murali, same lecture as the previous class Anna Ritz |

Wed, Mar 5, 2014 | Signaling Hypergraphs | Anna Ritz, same lecture as the previous class |

Student presentations |
||

Mon, Mar 17, 2014 | Review of NP-completeness | T. M. Murali |

Wed, Mar 19, 2014 | Optimal Traversal of Directed Hypergraphs | Michael Levet |

Mon, Mar 24, 2014 |
Linear
connectivity problems in directed hypergraphs Directed hypergraphs and applications |
Brendan Avent and Nitin Passa |

Wed, Mar 26, 2014 | Directed hypergraphs and applications | Brendan Avent and Nitin Passa, same presentation as the previous class |

Mon, Mar 31, 2014 | Finding the
K Shortest Loopless Paths in a NetworkFinding the K shortest hyperpathsFinding the K shortest hyperpaths using
reoptimization |
T. M. Murali Jose Cadena |

Wed, Apr 2, 2014 | Finding the K shortest hyperpathsFinding the K shortest hyperpaths using
reoptimization |
Jose Cadena, same presentation as the previous class |

Mon, Apr 7, 2014 | A Note on Menger's Theorem for Hypergraphs | Alexander Friedman |

Wed, Apr 9, 2014 | A Note on Menger's Theorem for Hypergraphs | Alexander Friedman, same presentation as the previous class |

Mon, Apr 14, 2014 | Flows on hypergraphs | Matthew Dallmeyer and Mohammed Davoodi |

Wed, Apr 16, 2014 | Matthew Dallmeyer and Mohammed Davoodi, same presentatin as the previous class | |

Mon, Apr 21, 2014 | Class cancelled | |

Wed, Apr 23, 2014 | Multilevel hypergraph partitioning: applications in VLSI domain | Doaa Altarawy |

Mon, Apr 28, 2014 | Normalized cuts and image
segmentation Learning with hypergraphs: Clustering, classification, and embedding |
Yeser Keneshloo |

Wed, Apr 30, 2014 | Learning with hypergraphs: Clustering, classification, and embedding | Yeser Keneshloo, same presentation as the previous class |

Mon, May 5, 2014 | Random walks in directed hypergraphs and application to semi-supervised image segmentation | Antuan Bualik and Tyler Kahn |

Wed, May 7, 2014 |
Random walks in directed hypergraphs and application to semi-supervised image segmentation | Antuan Bualik and Tyler Kahn, same presentation as the previous class |

# About the Course

- What is the focus of this course?
- Pre-requisites
- Course structure
- Papers to be covered
- How do hypergraphs arise in different domains? Molecular biology is an especially fertile source.
- What are appropriate ways to represent hypergraphs mathematically and computationally?
- How do we solve basic algorithmic problems on hypergaphs? Examples include shortest paths, random walks, and network flows.
- Can we reverse engineer hypergraphs from existing graph databases?
- How can we reinterpret datasets in areas such as molecular biology and social network through the lens of hypergraphs?

## What is the focus of this course?

Analysis of networks is ubiquitous in modern science, engineering, and the humanities. An overwhelming majority of these approaches use directed or undirected graphs in which edges connect pairs of nodes. However pair-wise interactions cannot accurately represent the manifold phenomena that involve coordinated activity of assemblages of more than two entities, e.g., a protein complex that acts as a unit or social interactions that occur among the members of a group such as a family or a criminal gang.Hypergraphs are emerging as an attractive alternative to graphs to represent such phenomena. Informally, a hyperedge (an edge in a hypergraph) is simply a connection among two or more nodes. Although hypegraph theory is a well-established area of mathematics, application of these concepts is relatively rare in network science. This course will discuss hypergraph theory, algorithms, and applications to answer the following questions:

## Course pre-requisites

Graduate work in algorithms, machine learning, or data mining will be very useful. Ability to program in a language such as Python, Matlab, or C++ is very important.## Course structure

The course will primarily be driven by lectures and by seminars where one or more students present a related group of papers from literature.

Your grade will depend on your presentation (20%), on class participation (30%), and a final project (50%). The final project is a group software project. I will define software projects that are inspired by the papers you present in class. The project will involve creating some new software or using existing software innovatively combined with some intensive analysis of the results. You are welcome to suggest a project to me.

## Papers to be covered

A CiteULike page collects a superset of the papers that we will discuss. The actual set of papers we will cover will depend on the interests of the students.*This list will evolve over the course of the semester.*