Questions tagged [network]
For topics related to network theory, which is a part of graph theory. Sub-topics include: Network Optimization & Network Analysis.
446
questions
1
vote
0
answers
11
views
Rewiring strategies to obtain networks with desired clustering coefficient and average path length
Note: this question was originally posted in the programming StackExchange, but as it is more of a conceptual/mathematical question, I am now posting it here.
There have been a few questions (and ...
1
vote
1
answer
29
views
Show inequality involving capacities of the union and intersection of cuts.
Let $(S,\overline S)$, $(T,\overline T)$ be cuts of a network $G$. I've alredy showed que $(S\cup T,\overline{S\cup T})$ and $(S\cap T,\overline{S\cap T})$ are cuts for $G$. Now, I have left to prove ...
- 2,117
2
votes
0
answers
22
views
Constructing a graph with a given Fiedler vector
Given $\boldsymbol u \in \mathbb{S}^{n-1}$, how could one construct a (weighted, connected) graph whose Fiedler vector $\lambda_{2}(D-A)$ — that is, a unit-norm eigenvector corresponding to the second-...
- 21
0
votes
0
answers
18
views
Questions to proof of Node law / cycle law / strength
I'm currently studying Proposition 9.4 (from "Markov chains and mixing times", written by Levin and Peres) regarding flow theory, specifically the proof provided, but I'm having trouble ...
1
vote
0
answers
21
views
Probability number of vertices in large component of Erdös-Renyi graph is close to survival probability
I am currently take a course on Erdös-Renyi graphs where we have the probability that two vertices are connected is given by $p = \lambda/n$ where n is the number of vertices of the graph G. Then one ...
- 114
1
vote
0
answers
28
views
Braess paradox: a network counterintuitive NE graph example
I cannot understand here why switching to
$CD$ is a dominant strategy??
If $x>4500$ then it may be beneficial for a Nash-Equilibrium to go from $C$ to $B$ and not from $C$ to $D$.
And hence $CD$ is ...
- 3,978
0
votes
0
answers
8
views
Finding a network such that two slight modifications of Edmond-Karp output different flows
Let $\mathcal{N} = (V, E, c)$ a network where $c$ is a function that maps edges to values in $\mathbb{R}^{+} \cup \{0\}$. Let $\Gamma^{+}(x) = \{y \in V : (x, y) \in E\}$ and $\Gamma^{-}(x) = \{y \in ...
- 3,468
1
vote
1
answer
17
views
In a directed series-parallel graph, is every pair of non-terminal nodes connected by at most one path?
The title pretty much says it all.
A directed graph $G = (V, E)$ is two-terminal series-parallel, with terminals $s_G$ and $t_G$, if it can be produced by a sequence of the following operations:
...
- 342
0
votes
0
answers
21
views
Does Flow Networks in Graph Theory includes latency or is it another model?
I studied graph theory at the university but "flow networks" were outside the course topics. While reading material about flow networks it is not clear for me if the latency concept (beyond ...
- 101
2
votes
0
answers
53
views
In search of a model to describe worm behaviour
For my bachelors thesis I am working with tubifex worms, and trying to develop a graph theoretical model that can help explain some mechanical and dynamical properties of the worms once they have ...
- 95
1
vote
1
answer
62
views
How to solve following binomial equation to get the assortivity?
Proving Assortativity r from Symmetric Binomial Distribution
Consider the symmetric binomial form given by the equation:
$$e_{jk} = N \binom{j+k}{j} p^j q^k + \binom{j+k}{k} p^k q^j$$
where $p+q=1$, $\...
0
votes
0
answers
34
views
Network graph: Given a network of n nodes, how to assign each node exactly r bidirectional connections?
I am a bit ashamed to ask this question. I work as a programmer, but my math is horribly bad.
It's not a programming question, as it's more related to graphs than actual code, that's why I decided to ...
0
votes
1
answer
47
views
Graph problem regarding Max-Flow Min-Cut while modifying capacity of an edge
Ok so i have the following problem, which is based on the Max Flow Min Cut Theorem:
Let $R = (G, s, t, c)$ be a transportation network, where $c : E(G) → Z^{∗}_{
+}$. Consider $e = uv ∈ E$
and $p ∈ Z$....
- 13
9
votes
1
answer
228
views
Sum of distance between integer numbers
Let $p$ is a positive integer, and let $A_1,\ldots,A_p$ be a partition of $\{1,\ldots,n\}$. My conjecture is that
\begin{equation}
\displaystyle\sum_{i=1}^p\left( \frac{\displaystyle\sum_{a_i,a_j \in ...
- 1,071
0
votes
0
answers
120
views
Unexpected Result from Finite Field Calculations in GF(2^8)
I'm performing calculations within the finite field $GF(2^8)$ and I can't seem to get the expected results. This is my first time working with finite fields, so my understanding is quite basic. I ...
