Network Topologies

Network topologies are the most basic graph structure guiding the way through highly complex networks. Nearly any complex system can be as a first modeling step visualised as a graph, either undirected (component A is in relation with component B), or directed (component A is influencing component B). The latter will establish the static basis for the further analysis of dynamical concepts, like feedback. There are fundamentally different network architectures, like exponential or scale-free networks. Small-world networks establish an architecture where information can potentially spread more easily over network paths than in any other type of network.

09:30am - 10:00am Registration at MRC, Zeeman Building, Mathematics Institute.

10:00am - 10:30am Welcome Reception, Mathematics Common Room.

10:30am - 11:00am Overview to workshop, Markus Kirkilionis and Ian Stewart

11:00am - 12:30am

Gesine Reinert (Oxford) - Predicting protein characteristics, protein interactions, and binding sites using network information, 45minAgnes Radl (Tübingen) - The commute distance on large random geometric graphs, 45min

12:30am - 1:30pm Lunch Break, Mathematics Common Room.

1:30pm - 3:00pm

Etienne Birmele (Genopole, Evry) - On random graph models and motif detection, 45min

3:00pm - 3:30pm Tea Break, Complexity Doctoral Training Centre, Common Room.

3:30pm - 5:00 Joint discussion

8:00pm - 9:30pm Joint lunch at Xanana (on Campus)

Abtracts:

Predicting protein characteristics, protein interactions, and binding sites using network information

by Gesine Reinert




Abstract: Protein interactions play a vital part in the functions of a cell. We propose to draw on interaction data using ideas from social network analysis to predict protein characteristics, and to predict and validate interactions in protein interaction networks. For predicting protein characteristics, an approach based on pairwise interactions only performs best, whereas for predicting interactions, exploring local clustering in the network proves beneficial; our method is based on three-way interactions. We also use a network-approach using amino acids as nodes to predict inter-domain binding sites. 




This is joint work with Pao-Yang Chen, Charlotte Deane, Rebecca Hamer and Qiang Luo.

---

The commute distance on large random geometric graphs

by Agnes Radl, Ulrike von Luxburg, Matthias Hein


The commute distance between two vertices of a graph is defined as the expected time it takes a random walk on the graph to travel from one vertex to the other and back. It is widely seen as a promising alternative to the shortest path distance because it takes global properites of the graph into account (e.g., the cluster structure in the graph). We study the behavior of the commute distance on a random geometric graph when the sample size increases. We find that as the
sample size tends to infinity, the appropriately rescaled commute distance between two fixed points converges to a non-trivial quantity. However, this quantity is not a meaningful graph distance any more. A similar result holds for the resistance distance, which measures the distance between two vertices in the graph in terms of their electical resistance in a corresponding electrical network. Using the commute or resistance distance on large random geometric graphs should thus be discouraged.

---

On random graph models and motif detection

by Etienne Birmele

Abstract: Studying biological networks from a statistical point of view requires the definition of a null model. The most popular way to do it is to sample a large number of graphs of same degree distribution than the biological one. We propose to use a mixture model of random graphs and show that it still fits the degree distribution by taking into account the preferential attachment phenomenon between groups of nodes. As an application, we propose to use this model to detect patterns of a network which are locally overrepresented with respect to their subpatterns. We show that the known motifs of the regulation network of Yeast are found again, with some more information about their structure.