Questions tagged [network]
For topics related to network theory, which is a part of graph theory. Sub-topics include: Network Optimization & Network Analysis.
435
questions
0
votes
0
answers
18
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 ...
- 89
1
vote
0
answers
24
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-...
- 1,829
2
votes
1
answer
49
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 ...
- 21
0
votes
0
answers
36
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'...
- 103
0
votes
0
answers
38
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}$ (...
- 101
0
votes
1
answer
107
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 ...
- 91
3
votes
2
answers
102
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$ ...
- 35.4k
0
votes
1
answer
48
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 ...
- 288
0
votes
1
answer
33
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 ...
- 3
2
votes
0
answers
34
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 ...
- 145
0
votes
0
answers
6
views
Projection onto the set of radiality contraints
Let $G$ be a graph of $n$ arcs and let $x\in \mathbb{R}^n$. I want to compute the orthogonal projection of $x$ onto the set of radial graphs with $k$ roots contained in $G$ (or a forest with $k$ root) ...
- 21
1
vote
1
answer
34
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 ...
2
votes
1
answer
43
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 ...
- 97
1
vote
0
answers
32
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(...
- 97
1
vote
1
answer
89
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 ...
- 97
0
votes
0
answers
45
views
graph homomorphism density inequality
I'm just reading the book "Large networks an Graph limits" by Lásló Lovász and I am trying to solve an exercise in the book. If $F$ and $G$ are two simple graphs, then their homorphism ...
1
vote
0
answers
16
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: ...
- 1,353
0
votes
1
answer
94
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 ...
0
votes
0
answers
27
views
Polynomial time algorithms for the 1-median location problem on general graphs
The 1-median problem is intended to find the location of a single facility on the network,
so that the total cost (the sum of the weighted distance of the vertexes) can be at minisum.
Hua (HUA, L. K. ...
- 61
0
votes
0
answers
18
views
Understanding the Role of Matrices in Capturing Disease Dynamics on Networks
I am currently reading an article related to Network epidemic, Markov chain and the relationship with automorphism graph, I'am confusing onp age 483: Here the link to the article
What are the ...
- 765
1
vote
1
answer
31
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 ...
0
votes
0
answers
35
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 ...
0
votes
0
answers
18
views
Web Service Markov Chain - state probability calculation
I have the following problem:
Let us consider a Web server software that fails at the failure rate gp, running on a machine (node) that fails independently at the failure rate gm. An automatic failure ...
0
votes
0
answers
77
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 ...
- 9
2
votes
0
answers
117
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:...
- 255
1
vote
1
answer
74
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 ...
- 515
1
vote
0
answers
37
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 ...
- 11
0
votes
1
answer
113
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 ...
- 1,361
0
votes
0
answers
61
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?
- 11
0
votes
1
answer
30
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 ...
- 704
2
votes
0
answers
114
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 ...
- 49
0
votes
0
answers
12
views
Are there recent review papers on random digraph models?
I am developing interest in random digraphs. I would like to have a quick survey of the history, concepts and latest developments in random digraph models. Is there some comprehensive contemporary ...
0
votes
0
answers
27
views
Help with a Street Network Problem
I have the following network:
It represents a street network that is to be patrolled by a police officer. It asks to find the length of his optimal route.
My first step was to find the total weight ...
0
votes
0
answers
12
views
What is an output feedback in a Echo State Network?
I don't know if this is the right place to address questions on this topic. I'm very new to machine learning and especially Echo state networks.
I was reading this article and there are many passages ...
- 704
0
votes
1
answer
37
views
Link probability Barabási-Albert Model
I am interested in a formula that describes the probability that nodes i < j < k of a BA model of size n (that have been added, respectively, at time i < j < k) are such that there is a ...
- 153
1
vote
1
answer
139
views
Initialization of the Network Simplex Method
I am studying Chapter 7 (Network Flow Problems) of the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. On page 286 the authors briefly describe a way to deal with the ...
- 629
0
votes
0
answers
51
views
Prove or disprove that a matrix has all elements in between (-1,1)
Let $X$ be an $N\times K$ real matrix and consider the $N\times N$ symmetric and positive definite matrix $\Theta = X(I + X'X)^{-1}X'$. It is not too difficult to prove that all elements of $\Theta$ ...
- 51
0
votes
0
answers
48
views
Feedback loops in Bayesian Network
I have been trying to understand and find information about "feedback loops" appearing in the graph when I used a Bayesian network with the algorithm grow-shrink. Knowing that BN can only be ...
- 1
0
votes
0
answers
19
views
Consider P:={x \in R^n|Ax=b} for A in R^m*n and b in R^m. Fix a point y in P that minimizes |supp(y)|. Prove that |supp(y)|<=m.
Consider P:= {$x\in R^n|Ax=b, x\ge 0$} for $A\in R^{m*n}$ and $b\in R^m$. Fix a point $y\in P$ that minimizes $|supp(y)|$ where $ supp(y):=$ {$j \in {1,..,n}|y_j \neq 0$}. Prove that $|supp(y)| \le m$....
- 1
2
votes
0
answers
98
views
Network that takes the form of a set of disjoint clusters or communities.
Consider the following simple and rather unrealistic mathematical model of a network. Each of $n$ nodes belongs to one of several groups. The $m$-th group has $n_m$ nodes and each node in that group ...
- 799
1
vote
0
answers
29
views
Dynamic complex multi-level loose-coupled networks
My request: I need advice on what to learn in order to solve the following problem.
My problem: I have a network, made up of multiple levels of nodes connected with weighted links. The network is ...
- 1,852
0
votes
0
answers
20
views
Network Flows - a cut
A really simple question that I cannot find a direct answer to. I guess it's considered so obvious but when finding a cut on a network flow graph (not necessarily min) can it cut an arc twice? TY
- 21
0
votes
1
answer
157
views
Showing that a discrete-time system has one equilibrium
I have the following discrete-time system:
$$x(k + 1) = Bx(k) + c$$
where $B \in \mathbb{R}^{n \times n}$ and $c \in \mathbb{R}^n$. Assuming $B$ is convergent, how can I show the following?
The ...
- 249
2
votes
1
answer
123
views
Induced Subgraph with the Largest Number of Edges
Is there an efficient way to find the induced subgraph with the largest number of edges among all the induced subgraphs of the same size?
For example, I have a 200-node graph H and I would like to ...
- 21
3
votes
0
answers
70
views
Is a network a category?
in this post on math.stackexchange, the top voted answer affirmed the following quote:
Roughly speaking, category theory is graph theory with additional structure to represent composition.
I am ...
- 131
1
vote
1
answer
35
views
Is it possible to generate a network with any number of vertex such that every vertex has equal degree
This definitely does not work for any number of vertex k and any number of degree n.
For example k=5 and n=3.
But how about other combinations?
- 158
1
vote
1
answer
42
views
Comparing network graphs
I started out with a grid graph,
performed some operations on it, and ended up with a set of networks; for example,
,
,
,
I need to compare these graphs.
A thought that I had was to compare them with ...
- 320
0
votes
0
answers
38
views
Comparing networks using graph theory
I'm new to graph theory so forgive if I use unconventional terminology. Please ask if there's any confusion regarding the statements I make.
I have a bunch of undirected, unweighted, simple graphs ...
- 320
6
votes
1
answer
107
views
Convergence of this finite difference sum on a small lattice
Consider the unit box $Q_1=[0,1]^3$ and the associated network of size $\epsilon$ : $\epsilon \mathbb{Z}^3 \cap Q_1$.
Let $W_\epsilon$ the set of functions $v : \mathbb{R}^3 \rightarrow \mathbb{R}$ ...
- 2,096
0
votes
1
answer
40
views
Determining the hubs in a small-world graph
How can you determine the "hub" nodes in a small-world graph especially when the degree distribution is fairly symmetric? I imagine what constitutes a hub or not is fairly arbitrary, or is ...
- 161