Skip to main content

Questions tagged [network]

For topics related to network theory, which is a part of graph theory. Sub-topics include: Network Optimization & Network Analysis.

Filter by
Sorted by
Tagged with
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 ...
Johannes Nauta's user avatar
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 ...
Fabrizio G's user avatar
  • 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-...
JakeH's user avatar
  • 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 ...
Susana Mena's user avatar
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 ...
GG314's user avatar
  • 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 ...
user122424's user avatar
  • 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 ...
lafinur's user avatar
  • 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: ...
graphtheory123's user avatar
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 ...
sw.'s user avatar
  • 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 ...
Rowan Potato's user avatar
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$, $\...
Nitish Kumar Sharma's user avatar
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 ...
unsafe_where_true's user avatar
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$....
Sparrow's user avatar
  • 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 ...
N.Quy's user avatar
  • 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 ...
DurangoOlsen's user avatar
0 votes
0 answers
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 ...
Marcus's user avatar
  • 1
0 votes
0 answers
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 ...
punypaw's user avatar
  • 487
3 votes
0 answers
90 views

Comparision cofactors of a matrix

Let $M=\begin{pmatrix} A & 0\\ 0 &B \end{pmatrix}$, where $A=[a_{i,j}]_{n\times n}$ and $B=[b_{i,j}]_{n \times n}$ are two square matrix of size $n$ with all non-negative entries. Assume that $...
N.Quy's user avatar
  • 1,071
0 votes
0 answers
93 views

Cayley tree reachable nodes proof

Imagine being in the central node of a Cayley Tree graph like this one: Cayle Tree, K =3 and D = 5 For a number of reachable t steps (t<D) prove that the reacheable nodes from the center equal: $$ ...
Cretheus7's user avatar
2 votes
0 answers
18 views

Number of vertices that are closer to the node that maximizes the closeness centrality.

I am trying to prove the following: "Let $\mathscr{G}(V, E)$ be a connected, unweighted, undirected graph with no self-loops or multiple edges and $n$ nodes ($|V| = n$). Suppose that there is a ...
sofiapontigo's user avatar
2 votes
0 answers
86 views

Mathematical definitions of in-degree and out-degree in a graph

Introduction. I have a kNN graph, which is a directed graph where each node $i$ has out-degree $k^{out}_i$. The out-degree $k^{out}_i$ is equal for every node $i$, and it is equal to the number of $k-...
Ommo's user avatar
  • 349
0 votes
0 answers
38 views

Can any 2d network be made up of a finite set of patterns at different locations?

This question is inspired by the physics of circuity. I was troubled by the assumptions of high school physics that we only need to know 2 laws. 1 is parallel circuit laws and 2 is series circuit laws,...
jg mr chapb's user avatar
  • 1,552
1 vote
0 answers
113 views

Probability Scenarios in a Communication Network with Link Failures

In the communication network given below, link failures are independent, and each link has a probability of failure p. (consider the physical situation). A can communicate with B as long as they are ...
Kelly's user avatar
  • 11
1 vote
0 answers
78 views

Electric Network and Random Walk: determine effective conductance

Suppose we have a network on $\mathcal{Z}^d$ with unit resistors between neighbouring points. Let $X$ be a simple symmetric random walk on $\mathcal{Z}^d$. I would like to prove that for any two ...
Enrico's user avatar
  • 563
0 votes
0 answers
25 views

Number of Iterations to maximize flow given recurrence relation

I have proven that there is always an augmenting path of capacity at least $\frac{F}{|E|}$. How do I use this to bound the number of rounds given that I use a relation to increase the flow by a ...
Money Mit's user avatar
1 vote
0 answers
61 views

Edge-Based Laplacian for directed graphs

Consider a directed graph $G$ and its node-to-edge signed incidence matrix $B \in \mathbb{R}^{n \times l}$ where $n$ and $l$ are the number of nodes and links respectively. I am interested in the so-...
Leonardo Massai's user avatar
2 votes
1 answer
359 views

Weighted degree centrality

I have a conceptual question about graphs which I couldn't find the answer to. I am calculating some node centralities and using them as features for a machine learning problem. I am using Networkx ...
gudé's user avatar
  • 21
0 votes
0 answers
61 views

Graph Alignment algorithms that consider both node and edge weights

I have two complete weighted graphs, with the same number of nodes and edges. Each node has a multi-dimensional vector, which represents its features. Edge weights are float numbers between 0 to 1. I'...
Danialz's user avatar
  • 103
1 vote
1 answer
112 views

Configuration model for weighted graphs for use in modularity formula

I cannot wrap my head around how the configuration model works if we have a degree sequence that has non-integers in it, i.e. we have edge weights $w\in \mathbb{Q}$ and nost just $w\in \mathbb{N}$ (...
Splines's user avatar
  • 111
0 votes
1 answer
398 views

clustering coefficient of a ring lattice

I'm reading through the following chapter and would like to prove their claim, that for a ring lattice, with parameter $k$. That means each nodes is connected to neighbours that are $k$ or fewer nodes ...
swissy's user avatar
  • 111
3 votes
2 answers
113 views

on average a random friend of mine has more friends than I do

Let $G=([n], E)$ be a finite graph with degree sequence $d=(d_v)_{v\in [n]}$. Assume $d_v\ge 1\;\forall v\in [n]$. Let $X_n$ be the degree of a vertex drawn uniformly at random from $[n]$, and $Y_n$ ...
Myshkin's user avatar
  • 36.3k
0 votes
1 answer
69 views

Is there a name for this type of graph that generalizes bipartite to general hierarchies?

Bipartite graphs have the property that there can only be edges between two subsets ("layers" as they usually depicted) of nodes. I am interested in the generalization of this to multiple ...
JohnA's user avatar
  • 288
0 votes
1 answer
74 views

Given the number of nodes, how can we find the total number of subgraphs?

I am reading Uri Alon's "Intro to Systems Biology" where he introduces the concept of subgraphs in networks. He claims that with 3 nodes, you can make 13 subgraphs, with 4 nodes 199 ...
Sigma123's user avatar
2 votes
0 answers
68 views

Distance/Similarity between two paths in a network

I have a weighted directed graph representing the intensity of movements of individuals between locations, with weights representing the mobility flow. I have another dataset consisting of particular ...
David Young's user avatar
1 vote
1 answer
40 views

How to efficiently solve a set of precedence networks at the same time?

I'm having a problem where I have a set of precedence networks. Each networks consists of a number of nodes which have a duration, and type. There are also a number of workers, who each have a type ...
IsolatedSushi's user avatar
2 votes
1 answer
45 views

Applying change of variable

I have the following function $$R_\infty = \sum_k P(k)[1-e^{-\lambda k\phi_\infty}$$ which is the infinite time epidemic prevalence of a network model for some degree $k$ in the network with infection ...
user1178472's user avatar
1 vote
0 answers
39 views

Solution to a network SEIR ODE system

I have the following network SEIR model: \begin{align} \frac{d}{dt} S_k(t) &= -\lambda kS_k(t) \Theta(t)\\\\ \frac{d}{dt} E_k(t) &= \lambda kS_k(t) \Theta(t) - \varepsilon E_k(...
user1178472's user avatar
1 vote
1 answer
91 views

Approximating/estimating values

I am working on a study of epidemic models for heterogeneous networks. I have the following expression $$1-e^z (1-z) + z^2(\gamma + \ln z + z + O(z^2))$$ where $\gamma$ is the Euler-Mascheroni ...
user1178472's user avatar
1 vote
0 answers
18 views

The minimum possible dimension of node embedding for network homophily

Background: Network homophily refers to the theory in network science which states that, based on node attributes, similar nodes may be more likely to attach to each other than dissimilar ones. (Ref: ...
Vezen BU's user avatar
  • 2,150
0 votes
1 answer
152 views

Seeking proof that the greedy algorithm is in fact the most optimal algorithm to construct graph with maximum variance in its degree distribution.

User inputs: number of nodes (n) and number of links (k). Objective: create an undirected (n,k) graph without multi-edges and without self loops that exhibits the maximum standard deviation in its ...
Aman Kabra's user avatar
1 vote
1 answer
34 views

A Hamiltonian cycles (plural) problem?

I'll be brief. I have a set of n vertices in a complete weighted graph, some of these vertices can be thought of as power plants and the rest as cities, and I need to find the shortest way to connect ...
Giuliano Cavallo's user avatar
0 votes
0 answers
56 views

Network Graph Theory Question

I have a small question regarding the following problem: Suppose that newborn nodes come in groups of n in each period. Suppose that they attach a fraction f of their links uniformly at random to ...
Stephen Moreton's user avatar
0 votes
0 answers
113 views

What is the stablished value for the modularity of the Karate Club?

The question speaks for itself. In the literature, we find that the karate club graph has a modularity value of 0.42. A python library to compute the modularity is networkx. To obtain the modularity ...
JFR's user avatar
  • 9
2 votes
0 answers
134 views

Tensorial Representation of a Complex Network (Questions on Tensors)

INTRODUCTION TO QUESTION 1 Some authors proposed a tensorial representation of complex networks (for both single layer networks and multilayer networks). One reference paper for this topic is this one:...
Ommo's user avatar
  • 349
1 vote
1 answer
93 views

Characterization of circular flow

We are given a directed graph $G$, capacity $u$, source $s$ and sink $t$. We call a flow from $s$ to $t$ a circular flow if the size of the flow is $0$. We say that function $l: E(G) \to R^{+}_{0}$ is ...
Hinko Pih Pih's user avatar
1 vote
0 answers
56 views

Did low-degree nodes tend to connect to other low-degree nodes in networks which follow power law with an exponential cutoff?

Question Take a power-law network with an exponential cutoff as an example: $$P(z)\sim z^{-\alpha} e^{-z/z_c}$$ where $P(z)$ is the degrees of nodes, $z$ is the order of nodes, $\alpha$ is the power ...
LI Bing's user avatar
  • 11
0 votes
1 answer
229 views

Stationary Distribution of a Random Walk

Consider the discrete time simple random walk $X_t$ on a finite connected graph with transition matrix $P$. At each step the walk moves to a neighbor uniformly at random. Assume that $X_t$ has a ...
domath's user avatar
  • 1,305
0 votes
0 answers
92 views

Why it is not possible to find a 3-colouring of this network, explain using pigeon hole principle.

I can explain why this network must have 4 colours at least but I am struggling to explain it using the pigeon hole principle could anyone help with an explanation?
Reilly Milne's user avatar
0 votes
1 answer
65 views

Ridge regresssion on a Echo State network

I am working with this article:http://www.scholarpedia.org/article/Echo_state_network on echo state networks. Here they speak about a ridge regression for the ESN. Normally the outputweight matrix ...
MarcoDJ01's user avatar
  • 690
2 votes
0 answers
120 views

What does near-cut (threshold) graph say about original complete weighted graph?

ORIGINAL post, preamble Start from a complete graph with weighted edges (e.g. in $[0,1]$ interval). Continuously increasing threshold $t$ from $0$ to $1$ drop edges with weights less than $t$. Finally ...
iLie's user avatar
  • 49

1
2 3 4 5
9