BIDS Announces GraphXD (Graphs across Domains)

September 25, 2017

Graphs (or networks) are composed of vertices connected by edges. Pictorially, a graph might be represented like this:

Graph with 5 vertices and 6 edges

Graph with 5 vertices and 6 edges

More formally, they can be represented as an ordered pair \((V, E)\) of vertices \(V\) and \(E\). In the above figure, the vertices \(V\) are \(\{1, 2, 3, 4, 5\}\) and the edges \(E\) are

\(\{\{1, 2\}, \{1, 3\}, \{1, 5\}, \{2, 3\}, \{3, 4\}, \{4, 5\}\}\).

While this example has undirected edges, graphs often have directed edges.

Graphs arise in many fields. A sociologist interested in social interactions in a community may record their observations in a graph of individuals connected by friendship. A geneticist interested in how genes are co-expressed may represent their data as a graph of genes with edges connecting genes that are expressed together. An online airline purchasing system may use a graph of airports connected by edges with direct flights between them.

Graphs enjoy widespread attention in applied as well as theoretical domains. Mathematicians are still making tremendous advances in understanding their structure and properties, while computer scientists are developing efficient and breakthrough algorithms to analyze them. Moreover, algorithmic advances are occurring in a variety of application domains.

Despite their seeming simplicity, we are still learning a lot about graphs. In the picture above, it is easy to see what is going on visually. However, in practice, graphs are often too large and too complicated to visualize: just imagine attempting to extract information from a graph composed of 30,000 genes and 100,000 interactions. More automated methods to analyze graphs and extract meaningful information from them are often required.

Progress in understanding graphs and developing new graph algorithms in a number of diverse fields is hindered by the fact that researchers who use them typically don’t have the opportunity to communicate with others who work on similar problems in different domains.

Graphs across Domains (GraphXD) is a BIDS project that aims:

  • to foster a community of shared interest from disparate fields including mathematics, computer science, statistics, physics, biology, sociology, and any other field with an interest in graph data;
  • to develop a shared vocabulary and identify common principles, algorithms, and tools for understanding graphs; and
  • to learn from one another while strengthening ties across disciplinary boundaries.

GraphXD connects scientists, researchers, and theorists interested in graphs from a variety of fields through:

1. A seminar series - Once a month, the Berkeley GraphXD community gets together from 5:30 to 7:00pm in Evans room 1011 for an informal presentation on open questions, new results, old results worth remembering, or whatever is fit to entertain a crowd of scientists, researchers, and theorists interested in graphs.

2. An annual workshop - This spring, BIDS will host a three day inaugural workshop (March 27–29, 2018). Topics will include interesting graph data, graph algorithms, as well as software for creating, manipulating, and studying the structure, dynamics, and functions of complex networks. Depending on interest, we may also host a one day software bootcamp focused on Python and NetworkX prior to the workshop.

If you are interested in GraphXD, please join us for our first seminar talk this Thursday (9/28) and feel free to sign up on our announcement email list.