# 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
Filter by
Sorted by
Tagged with
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 ...
1 vote
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-...
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 ...
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'...
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}$ (...
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 ...
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$ ...
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 ...
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 ...
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 ...
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) ...
1 vote
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 ...
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 ...
1 vote
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(...
1 vote
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 ...
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
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: ...
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 ...
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. ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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:...
1 vote
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 ...
1 vote
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
37 views

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 ...
1 vote
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 ...
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$ ...
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 ...
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$....
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 ...
1 vote
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 ...
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
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 ...
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 ...
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 ...
1 vote
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?
1 vote
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 ...
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 ...
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}$ ...