Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
This site is currently in read-only mode; we'll return with full functionality soon. Follow @StackStatus or visit our status blog for more info.

Questions tagged [network]

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

0
votes
0answers
10 views

Calculating utilization of BITMAP protocol

i was reading around and didn't find any solution to my problem, either here in stackexchange, nor in recaps and tutorials online, so i am trying posting it here, hoping that i might get lucky and ...
0
votes
0answers
18 views

Find a matrix that describes a modularity score of a partition.

For a partition P of a network of n nodes and m edges into two disjoint communities, $V_{1}$ and $V_{2}$. Let $s=[s_{1},s_{2},...,s_{n}]$ where each $s_{i}$, corresponding to each vertex is 1 if that ...
2
votes
0answers
22 views

Path finding in time dependent graphs and murderous hitchhikers

Last week I heard some informatic students talking about car-to-car communication via wifi-hotspots in cars and the following problem occured to me: Suppose you are making a road trip with many ...
2
votes
0answers
26 views

books recommendations for discrete pde

I am a beginner of discrete PDE (PDE on graph)! Is there any book for discrete PDE which specifies the concept of differentiation and integration, laplacian and solving hyperbolic, parabolic, elliptic ...
0
votes
2answers
23 views

Name for network in which nodes only have two different degrees

What is the name for a network that only admits two different values for the degrees of its nodes? For example you might have a graph with degree sequence, $D=(12^4,4^{100}).$ The notation means ...
0
votes
1answer
18 views

What is the sum of degree centrality called?

I have used the sum of degree centrality, which is the sum of all the edges in an undirected network, as a feature for a machine learning algorithm. But I am not sure if there is any terminology for ...
2
votes
1answer
29 views

Is counting the frequency a vertex appears in paths between all vertexes a valid way to determine “centrality”?

I have a blog with 15+ years of posts. There are over 7,000 of them. (It's Gadgetopia, if you're curious.) I'm auditing it in preparation for a big purge, and I'm accumulating some metrics so I can "...
0
votes
0answers
13 views

How to evaluate homogeneity of a distribution (nodes among a graph's communities)?

Suppose I have a distribution A of nodes in communities of a network graph: 0 29 1 28 2 23 3 22 5 20 4 20 6 8 Then I have another ...
2
votes
1answer
66 views

Can we calculate a differential difficulty score of claiming colored vs. uncolored routes in "Ticket to Ride?

The board game Ticket to Ride is a train-themed exercise in graph theory. The game has cities (nodes/vertices) which are connected by routes (links/edges). Each route has two characteristics: Length,...
2
votes
0answers
17 views

Is there a generative network model for arbitrary distributions that guarantees an edge count?

So what I am trying to do is rewire a random directed graph (specifically a boolean network) so the out-degree distribution is scale-free. However I need a generative model that will allow me to ...
0
votes
0answers
46 views

Meaning of (viable) and (non viable) flow pattern?

I found all the unknown traffic flows for this network (check picture), but in the end, the question is asking to give (one viable flow pattern) and (one that is not viable) what does that mean? any ...
0
votes
1answer
98 views

Given an n*n adjacency matrix, calculate the number of triangles in a graph

I got that if we calculate the eigenvalues of the adjacency matrix of the graph, and then sum all of the eigenvalues, then it will give the number of triangles in the graph. Is this true, if not then ...
0
votes
0answers
34 views

Help with connection between Eigenvalues and triangles

What is a "triangle" in a graph, and what is the formula for calculating the number of triangles in a graph using the eigenvalues of the adjacency matrix. Any help will be much appreciated,
1
vote
0answers
242 views

Computing the distance matrix from an adjacency matrix

How do I do this? I know how to compute each matrix from a given graph but don't know how to get from one to the other and what the link between the two matrices are. PS: for graphs that are ...
0
votes
0answers
12 views

How the degree centrality measure changes in the presence of loops?

I am using R with the igraph package to make some experiment. In particular I am making a star graph. So I build a graph with 5 nodes, 4 of them connected to the central node and nothing else: ...
1
vote
0answers
25 views

Ring network Bernoulli with conversion rule

Imagine there is a ring network $G$ with $N$ (odd) nodes. Nodes are initially $iid$, $a_i\overset{\text{iid}}\sim Ber(p)$. However, once the value is assigned, a node with $a_i=0$ will switch to $1$ ...
0
votes
0answers
19 views

Graph theory: can a node's edge 'connect' directly to another edge in a unidirectional manner?

As will be apparent, my familiarity with graph theory is somewhat limited; I haven't been able to find a reliable answer to this question, which may well be incorrect phrasing on my part. My question ...
2
votes
1answer
49 views

Matrix algebra needed to derive tricky equation… Trophic levels and networks!

Imagine a food web (a directed, acyclic network) where the nodes are species and the edges represent predator-prey relationships. Prey nodes have an edge directed to the predators that eat them. ...
0
votes
0answers
25 views

How to sum over all allowed values of adjacency matrix?

I have troubles to understand the following simplification. $\sum_{\{A_{ij}\}} \Pi_{i<j} e^{\lambda A_{ij}} = \Pi_{i<j} \sum_{A_{ij =0,1}} e^{\lambda A_{ij}} $ How am I allowed to move the ...
0
votes
0answers
20 views

How is delta value determined in this transshipment problem?

I am trying to understand how this transshipment problem is optimized from step to step. I have the answer on the exercice, but cannot really get it. The main point is clear: We want to transport (in ...
1
vote
0answers
16 views

Algorithm for Generating Hourglass Networks

Are there any known algorithms that can generate random networks with the shape of the well known 'hourglass' (sometimes called bowtie) network? More specifically, is there's an algorithm which ...
1
vote
0answers
19 views

It is possible for the nodes of a network to have a different total cost. If they have the same value in degree centrality?

I do same simulations with randoms networks and for each network and calculates different measures such degree centrality. In the network is likely more than one node to have the highest degree value. ...
2
votes
1answer
160 views

Shortest path between nodes in a graph with multiple sources and destinations? (No collisions.)

Dijkstra's algorithm is a well-known method for finding the shortest path between two nodes in a graph. For instance, let's say that we have a graph like this: base graph Imagine that we want to ...
0
votes
1answer
57 views

How do you estimate the remaining degree distribution?

Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either end of a randomly chosen edge. Let $G=(V,E)$ be an undirected graph with nodes $V=(...
2
votes
1answer
39 views

Proof of a graph theorem

Studying graph theory I found the following theorem for s,t vertex of the graph $G=(V,E)$ and a cut defined as "subset $C$ of $E$ an s−t cut if C = $δ ^{out}(U)$ for some subset U of V satisfying s $\...
0
votes
0answers
84 views

Why is the (undirected) remaining degree distribution symmetric in its indices?

I am trying to calculate the remaining degree distribution of an undirected graph. Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either ...
1
vote
1answer
59 views

Split network flow function

Let a graph $G = (V,E)$ a network $N = (G, s, t, c)$ and an integral flow funtion $f$ The value of f $v(f)=v_1+v_2+...+v_p$, where $v_i$ is a flow leaving the source. I must prove that there are $p$...
0
votes
1answer
18 views

How to calculate the Delay Formula (clarify the formula)

I would like to understand how their respective answers were reached, this is a question in my current class and everyone in the class has A-Level mathematics experience - I have asked my tutor to ...
-1
votes
1answer
34 views

Does the dimension converge? [closed]

I'm doing an exercise in a textbook and I need to calculate the effective dimension of a possibly non-Euclidean network lattice. I have $r^d=2r^2+2r+1$ where $d$ is the dimension of the network and I ...
0
votes
0answers
35 views

Transport/flow network in GAP

How to define a transport network in GAP? I can't seem to find a single function related to transport networks or flows in general in the GAP-GRAPE manual. I'd be content with just manually adding ...
0
votes
1answer
17 views

Characteristic Path Length for a 1-lattices

I do not understand how to obtain the stated formula for the characteristic path length (L) of a $1$-lattice, as well as its clustering coefficient. The following text is taken from The Small World ...
0
votes
1answer
17 views

Mathematical algorithm for graphs

I would like to make a computer program that would give the fewest number of nodes needed to make a graph traversable. When a node is 'on' all the arcs coming off it are reachable until the next node. ...
0
votes
1answer
18 views

How to solve delay calculations, namely propagation delay and transmition delay (Clarify the formula)

I have a big exam coming up in January and a small portion of it is on Delay calculations. My tutors are not very helpful when it comes to this so I was wondering if I could get some help with[enter ...
1
vote
1answer
31 views

Defining the connectivity of a graph

Consider a simple binary undirected graph, which adjacency matrix is $A = \{a_{i,j}\} \in \{0, 1\}^{N \times N}.$ Suppose that all vertices of such graph have at least one neighbors, i.e. $$k_i = \...
1
vote
1answer
27 views

Effective conductance is symmetric

Given a network $G$, and states $x$, and $y$, I want to show that $\mathscr{C}(x \leftrightarrow y) = \mathscr{C}(y\leftrightarrow x)$ I know that $ \mathscr{C}(x \leftrightarrow y) = \pi(x)P(x\...
0
votes
0answers
30 views

Network robustness

I have 10 nodes in my network. I calculated the size of the largest component in my network, using the below formula: Size of the largest component (when node 1 is deleted) = Number of nodes in the ...
0
votes
0answers
56 views

Feasible Flows and Incidence Vectors

Let $f$ be a function on the arc set $A$ of an acyclic network $N(x,y)$ (here $x$ is the source and $y$ the sink). Suppose $0 \leq f(a) \leq c(a)$ for all $a \in A$ ($c$ is the capacity function). ...
-1
votes
1answer
39 views

understanding iterated function system by Markov chain [closed]

The Iterated Function System at node $i$ is a discrete time Markov chain on the state space ${\cal S}_i=\mathbb{R}^d$. The chain is specified by an integer $m$ and a collection of maps $f_j^{(i)}: ...
1
vote
1answer
32 views

Connectivity of random network

I'm interested in the following (pretty open-ended) problem : Say we have some network of $n$ nodes, labeled by integers $i\in\mathbb{Z}/n\mathbb{Z}$. Each node $i$ chooses a random subset $\mathrm{...
0
votes
1answer
39 views

True or False: Flow network with $n$ internal nodes has $2^n$ different cuts with all min capacity

Prove whether true or false: For every $n >0$, there exists a flow network with $n$ internal nodes such that there are $2^n$ different cuts that all have minimum capacity. I have no idea how to ...
0
votes
0answers
17 views

Is there an aperiodic tiling such that approximates space?

Many aperiodic tilings still have some preferred directions. Think of penrose tilings. Imagine turning a tiling into a network and finding geodesic paths through the network. Are any tilings in 2 3 or ...
1
vote
0answers
29 views

Benes and Butterfly network mash-up

Been trying to sketch this network to work on a problem, I think I found online something that might be it, but I'm not sure. the network goes like this: "The i th input switch in a Reasoner-net ...
0
votes
0answers
19 views

Proving Easy Lemma about Flows

Let $D=(V,E)$ be some basic flow network and $f$ some flow. I'm trying to prove the following lemma: I've been told that this is a proof that follows directly from the definitions of flow yet I can't ...
0
votes
0answers
9 views

Applications of high mean escape time subgraphs

I am learning about algorithms for finding subgraphs with high mean escape time, and I am wondering if someone could enlighten me on what applications there are for such a task. Applications to either ...
0
votes
0answers
29 views

What are the Nash equilibria of this network?

Braess's Paradox provides an explanation for why traffic can worsen after new roads are added. For example, consider traveling from A to B in the following network: Cars dividing equally between the ...
1
vote
0answers
24 views

Example of a network with negative modularity?

I'm trying to self-learn network analysis. It is very abstract to me how a negative network can be constructed based on the formula of Modularity. Version 1 or Version 2. Version 1: $Q=\frac{1}{2m} \...
0
votes
0answers
8 views

Calculate average retransmissions in communications

In an network, when transmitting a packet, it can be rejected by a first router with a probability p. Then It can also be rejected by a second router with the same probability p. We have something ...
0
votes
0answers
33 views

Measure network division by summation of clusters

I'm new to network data and is having trouble making connections between Louvain Modularity in the sum of vertex with the form condensed to sum over the cluster. I'm trying to prove 1) $Q=\frac{1}{...
1
vote
0answers
32 views

How does PageRank deal with nodes that do not have out-links?

I will use the notation that $A_{ij}=1$ if an arrow exists from $j$ to $i$ and otherwise zero. Just to avoid confusion I use in brackets the standard convention $B_{ij}=1$ when $i$ has a directed ...
1
vote
0answers
230 views

Sum of the degrees of second neighbours of a vertex in a graph

The question is: "Using only matrix formalism find the vector $\pmb{v}$ whose element $i$ is the sum of the degrees of vertex's $i$ second neighbours". My attempt: Let $A$ be the adjacent matrix ...