## Contributed Session Thu.2.H 2013

#### Thursday, 13:15 - 14:45 h, Room: H 2013

**Cluster 11: Integer & mixed-integer programming** [...]

### Network analysis

**Chair: Stefan Wiesberg**

**Thursday, 13:15 - 13:40 h, Room: H 2013, Talk 1**

**Xavier Molinero**

Variations in strict separating systems representing a linearly separable function

**Coauthor: Josep Freixas**

**Abstract:**

An important consideration when applying neural networks is predict the effect of threshold and weight perturbations on them, i.e., which is the sharpest bound one may consider for weights and threshold to maintain the linearly separable function unchangeable for designing a more robust

and safer neural network.

Two parameters have been introduced to measure the relative errors in weights and threshold of strict separating systems: the tolerance (Hu 1960) and the greatest tolerance (Freixas and Molinero 2008). Given an arbitrary separating system we study which is the equivalent separating system that provides maximum tolerance and maximum greatest tolerance.

We present new results for the maximum tolerance and the maximum greatest tolerance, for instance, we present when the maximum tolerance and maximum greatest tolerance among all equivalent strict separating (natural) systems are attained.

We also give the strict separating (natural) system that attaches the maximum tolerance for n variables. Similar results appear for the maximum greatest tolerance.

Finally, we also give new results for the number of variables n and the number of types of distinguished variables *k*.

**Thursday, 13:45 - 14:10 h, Room: H 2013, Talk 2**

**Arne MÃ¼ller**

Cycle free flows in large-scale metabolic networks

**Abstract:**

Genome-scale metabolic networks are used to model all (usually around 2000) chemical reactions occuring in a biological cell. These networks are a generalization of directed hypergraphs (where the reactions are the arcs of the graph) and a specialization of realizable oriented matroids.

We are interested in optimizing the flow through a given reaction in the network. We have the usual constraint of flow conservation and additionally the flow must not contain internal circuits. Internal circuits are flows that do not contain a specific subset of the reactions called exchange reactions.

We show that it is NP-hard to decide if a non-zero flow without internal circuits through a given reaction is possible. However, most genome-scale metabolic networks only contain few internal circuits. Using a specific branching strategy combined with a primal heuristic, we derive a tractability result that is also practically applicable. In fact, it very often suffices to solve only one LP.

For flux variability analysis, where we solve optimization problems for each reaction in the network, we obtain a speed-up of factor *30-300* to previous methods.

**Thursday, 14:15 - 14:40 h, Room: H 2013, Talk 3**

**Stefan Wiesberg**

Computing role structures in networks

**Coauthor: Gerhard Reinelt**

**Abstract:**

In network analysis, an established way to obtain structural information is to partition the vertices into so-called regular equivalence classes. In such a partitioning, two nodes *u* and *v* belong to the same class if for every neighbor of *u*, there is a neighbor of *v* in the same class, and vice versa. Thus, for any two classes *C* and *D*, either every or no member of *C* has a neighbor in *D*. The relationships between the classes can hence be visualized by a graph, the so-called role graph. It is of interest in several fields, for example in sociology, economy, or consumer research.

An NP-hard problem in this context is the following one: Given a network *G* and a finite set *R* of role graphs, which element of *R* represents the role structure of *G* in the best possible way? We present one of the first exact algorithms for this problem. It is based on an IP formulation with a quadratic objective function and solved by branch-and-cut. Significant running-time improvements compared to currently used methods are reported.