# 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
Filter by
Sorted by
Tagged with
1 vote
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
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
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
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
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
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
8 views

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 ...
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
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 \displaystyle\sum_{i=1}^p\left( \frac{\displaystyle\sum_{a_i,a_j \in ...
• 1,071
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 ...
25 views

### Generating network centrality measures - should incoporate directed ties from unidentifiable nodes?

I have classroom network data where kids named their friends in the classroom (a directed network). I'd like to measure the closeness and betweenness centrality of each kid within their classroom. In ...
28 views

### How to reduce a problem to feasible circulation/network flow, in the case of cyclic dependency

Background: Given a set of vertices and conditions, in order to see if all the conditions can be met, I want to reduce it to a circulation problem such that all the conditions in the original problem ...
• 487