# Graph algorithms for vulnerability and optimality of network

I am studying a research paper which is concerned with finding paths from a source nodes to a single sink node keeping in mind 2 things.

1.The security of the path.

2.The optimality of the path.

The vulnerability model of paper says that the link that is shared by greater number of paths is more vulnerable to be attacked by some attacker. For example if there are 5 source nodes and 1 sink node, and say there is a link shared by 3 out of 5 paths and a link shared by only 1 out of 5 paths, then the latter link is more secure.

It basically defines the vulnerability of a link by the value of $No(e)$, where $e$ is the edge and it applies a constraint that the link cannot be used by more than $No(e)$ paths for the link to be secure, other wise it is likely to get attacked.

Here are important points about the research paper.

To guarantee network security, the constraint vulnerability for each link $e$ is set to $No(e)$, which is a positive integer.

$s$ is the single sink node and $P$ is the set of sources.

Definition 1: An $s-P$ cut (Ecut) is defined as the set of links satisfying that if these links are removed, node $s$ and nodes in set $P$ are disconnected, meaning all the sources will be disconnected from the sink node. The weight of $s-P$ node cut is defined as

$\sum{(No(e))}$ $\forall e \in$ cut $s-P$.

The $s-P$ node cut with minimum weight is defined as $C_{min}$. This also serves as the upper bound for the number of sources allowed to transmit, or mathematically it means

$$|P| \leq C_{min}$$

Up to this point I have understood it completely. The upper bound on $|P|$ can be very easily derived, by analysing the boundary condition. Suppose we allow exactly $C_{min}$ number of sources to transmit and $C_{min} = \sum{No(e)}$ for all the edges in the cut with minimum weight. Now say $No(e)$ paths go through first edge in the cut, No(e) paths go through second edge in the cut and so on. But if anywhere $No(e)+1$ paths go through an edge keeping everything same(or in other words having sources $C_{min} + 1$) then vulnerability constraint is broken as link can at most be used by $No(e)$ paths.

Further the research paper is:Which I am not comfortable with is

Proposed Algorithms

Let us use a strategy to convert undirected to directed graph with the objective of devising an algorithm with the help of network flow theory.

For each link $(u,v)$ in graph, replace it by two directed arcs, $(u,v)$ and $(v,u)$, the cost of both arcs is same as cost of link in undirected graph. Let us denote the new network with $G(N,A)$, $E$ being replaced by $A$.

Now for each directed arc $(u,v) \in A$, we define $f(u,v)$ as the current unit flow from node $u$ to node $v$. We initialize $f(u,v)$ as $No(u,v)$.

Algorithm 1: Computing the number of source nodes using each arc for the data transmission. I understood that the number of source nodes using an arc for data transmission(or the number of times an arc is being used in various paths) is

$$r(u,v) = |No(u,v) - f(u,v)|$$

But my question is why was the need for arcs, we could have applied the dijkstra on undirected graph and then could have also got this, what is that I am missing.

Further the paper proposes that the cost $r(u,v)$ is added to each link in the undirected graph but does not specify whether both $r(u,v)$ and $r(v,u)$ is added The second alogirthm, which i could not understand as to why the deletion of links is happening and also minimal explanation in paper of it is given. Can somebody explain the second algorithm and its link with the first one and try to explain the bigger picture so that I can understand what is going on.

• What is your question? It's not clear to me what specifically you are asking. "Can someone explain the algorithm?" is not a good fit for this site as it's too open-ended. What specifically is your confusion/uncertainty? What have you tried? You say that you are uncomfortable with it but you haven't told us what specifically is confusing you. Have you tried running the algorithm by hand on some small examples? Have you tried proving it correct? What are your thoughts? (cont.) – D.W. Jan 29 '16 at 20:43
• The paper makes some claims about the algorithm (see Prop 2) so that should give you some picture of what it's trying to achieve. Also, please edit the question to give a full citation to the paper (title, authors, where published), so that if the link stops working, we can still work out what paper you're asking about. Thank you! – D.W. Jan 29 '16 at 20:43
• @D.W. Did u even read my question sir? – Sumeet Jan 30 '16 at 7:07
• Part of becoming a researcher in computer science is being able to read papers. Not all papers are well written, and often papers contain mistakes. Also, sometimes papers can be improved. These are all issues that your advisor can perhaps help you with. – Yuval Filmus Jan 30 '16 at 8:38
• If you are a practitioner, it is still better to try and understand the paper, since usually some corner cases are not covered by the pseudocode, or perhaps the pseudocode is just wrong since nobody ever programmed it. However, in that case perhaps you shouldn't worry too much about why the authors chose one thing over another – unless you need to improve their algorithm. – Yuval Filmus Jan 30 '16 at 8:40