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
2 votes
0 answers
18 views

Leontief inverse in undirected network [closed]

I sort of understand how the Leontief inverse is measured and where it is used. Though it occurred to me whether it makes sense to use this approach in undirected networks (e.g. correlation matrix).
user avatar
  • 249
-3 votes
0 answers
24 views

Who is the most important person in this dataset? Centrality [closed]

I have a dataset and data represent people and their followers on social media. I need to conduct social network analysis. Can you help me to identify most important person and calculationg the Degree,...
user avatar
0 votes
0 answers
16 views

Measure the connection between two subgroups of nodes in directed graph.

I have task to do in my work about cooperation of departments basing on related webpages on domain website. Abstractly speaking I have directed graph $G$ and $n$ subgroups of nodes. Now I want to get ...
user avatar
  • 69
0 votes
1 answer
19 views

The Curie-Weiss model from Ising

Can anyone explain why this is the case? $$ \begin{aligned} p(\mathbf{x}) &=\frac{\exp \left\{\sum_{i=1}^{n} \mu_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=1}^{n} \sigma x_{i} x_{j}\right\}}{\sum_{\mathbf{x}...
user avatar
  • 13
0 votes
0 answers
7 views

Influence of conditioning a node in an undirected graph on other nodes

Assume that I have a $D$-variate random variable $\mathbf{X}$, and a $D$-by-$D$ precision matrix denoting the strength of an undirected graph's edges between each of its $D$ univariate nodes (where ...
user avatar
  • 855
0 votes
0 answers
17 views

Find the upper bound probability of a collision in a packet scheduling problem - Exercise

Let $G$ be a graph representing a network. On this network we have $N$ packets, each with a starting node, a path and an end node. Time is discrete, so each packet move only at a certain instant. When ...
user avatar
1 vote
1 answer
24 views

Simplification of a logarithm in the context of a network

I am reading Mark Newman's Networks textbook and equation 11.14 is puzzling me. $$ \ln{u} = (n-1)\ln{\Big[ 1 - \frac{c}{n-1} (1-u) \Big]} \\ \approx -(n-1)\frac{c}{n-1}(1-u) $$ With my understanding ...
user avatar
0 votes
1 answer
19 views

Average of maximal flows and each arc's level of saturation

I am going through the proof of the max-flow min-cut theorem presented in the following paper: Ford, L., & Fulkerson, D. (1956). Maximal Flow Through a Network. Canadian Journal of Mathematics, 8, ...
user avatar
4 votes
0 answers
82 views

Minimum number of 4-way switches to allow any pairing of $N$ inputs

I want to build a network of switches that with $N$ inputs that allows any pairing of the inputs to be created ($N$ is an even number). For each number of inputs, I'm looking for a network with the ...
user avatar
0 votes
0 answers
17 views

Extinction condition for Leslie matrix

Good morning, I assume that I have an irreducible Leslie matrix s.t.: $$ \begin{pmatrix} 0 & \alpha_2 & ... & ... & \alpha_n\\ \beta_1 & 0 & ... & ...& 0\\ 0 & \...
user avatar
-1 votes
1 answer
29 views

Solving system of linear equations across network in Python [closed]

I have a network and I would like to calculate the voltage drop across the nodes (2-5). I know V1=10 and V6=0. The equations at ...
user avatar
  • 3
0 votes
1 answer
31 views

Calculation for the entropy of binomial random graph

In my classes, we found that for a graph $\mathbf{a}\in G(n,p)$, where we have labelled the graphs by their adjacency matrices, $P(\mathbf{a}) = \prod _{i<j}p^{a_{ij}}(1-p)^{(1-a_{ij})}$ We define ...
user avatar
  • 2,947
0 votes
0 answers
121 views

Calculate an optimal value of probability p such that the average power consumption of the node is minimized.

Consider time slot data transmission from a base station to a node. In each time slot, the base station transmits a packet with probability $0.4$. The node can be in the active mode and can receive ...
user avatar
1 vote
0 answers
10 views

Question on the betweenness centrality and min-cut in network theory

all! I have a question about the network theory. I want to figure out whether there is a correlation between the min-cut of a network and the betweenness centrality measure in a network. With respect ...
user avatar
  • 21
0 votes
0 answers
17 views

Which algorithm to try on a huge graph for a community detection task?

I have a messy huge connected directed graph with ~90k nodes and ~850k edges, so louvain is one of those few algorithms that can be fairly fast to run on such big graphs to find network communities. ...
user avatar
  • 1
0 votes
1 answer
23 views

What does the rewiring probability for a small-world network indicate?

A large rewiring probability for a small-world network means the network has more randomness. Does this mean anything deeper, and can it be determined for a real (i.e., empirical) network?
user avatar
0 votes
0 answers
16 views

Different families of small-world networks?

I am trying to understand the small-world network phenomenon. In the original paper by Watts and Strogatz, they study the family of small-world networks starting from an idealization of a regular ring ...
user avatar
0 votes
0 answers
12 views

Algorithmically find the maximal flow of a capacitated network using the max-flow min cut theorem.

I've worked through a proof of the max-flow, min cut theorem. Visually it is easy to find a minimum cut of a network. Is there an algorithmic way for a computer to find one? I have seen some mentions ...
user avatar
1 vote
1 answer
22 views

Homomorphism densities for kernels generalizes the simple graph case

I am studying the well-written book Large networks and Graph Limits by László Lovász (you can find it here). If $F$ and $G$ are two simple graphs, then their homomorphism density is defined as $t(F,G) ...
user avatar
  • 215
1 vote
0 answers
68 views

Mathematical Formalism/Framework which describes the Internet [closed]

I have searched for about 30 mins for a purely mathematical/logical description of the internet but I haven't found anything I'm looking for so I have decided to invoke the collective wisdom of stack ...
user avatar
1 vote
0 answers
46 views

Why to normalize an adjacency matrix?

In Kipf & Welling (2017) paper https://arxiv.org/pdf/1609.02907.pdf. It uses the normalized adjacency matrix $\mathbf{A}_{symm} = \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$. I know the largest ...
user avatar
  • 123
1 vote
1 answer
38 views

Interpretation of an undirected adjacency matrix

I am new and know not much about "graph theory" and "graph neural network". Assume, I have one incidence matrix $\mathbf{B}$ such as visitor item1 item2 item3 item4 A 1 0 0 1 B ...
user avatar
  • 123
0 votes
0 answers
15 views

Function of the Degree Centrality in Tree Graphs

Determine the normalised degree centrality of the nodes in some random trees. What do you observe? E.g., is there some function of the degree centrality that is constant across your examples? I've ...
user avatar
  • 1
0 votes
1 answer
54 views

Random walk on a weighted undirected graph with self loops

I am writing a tutorial paper about the use of Markov chains / random walks on graphs in machine learning. Since I want to demonstrate that any Markov chain can be realized by a random walk on some ...
user avatar
  • 11
0 votes
0 answers
29 views

How to calculate Information Dimension

I am trying to implement this paper by Tian Bian and Yong Deng. In this paper, after applying probability they have gotten information entropy values $l_a(r)=(1.3741,0.6930,0.6385,0) , (r=1,2,3,4)$ ...
user avatar
-1 votes
1 answer
95 views

Show that every strict acyclic digraph contains an arc whose reversal results in an acyclic digraph. [closed]

I was self-studying Bondy's book on graph theory and I was stuck in this question. can anybody help me? a strict acyclic digraph is a digraph that if node i and j are connected and if j and k the node ...
user avatar
1 vote
0 answers
15 views

Ergodicity regarding links in networks

I am reading this article where it explains an ergodic assumption regarding links but I do not quite understand what the autor means. The “ergodic assumption” of random link switching is of course ...
user avatar
0 votes
0 answers
17 views

Algorithm to create square Boolean (adiacency) matrices satisfying certain conditions.

Given a square nxn Boolean(0,1) matrix M equal to its transpose with trace=0, consider the sum $s_r$ of the elements $e_{r1}$,..,$e_{rn}$ of any row r where the elements $e_{ri}$,..,$e_{rj}$ are "...
user avatar
  • 197
5 votes
0 answers
85 views

Bounds on Cut Sizes on an Erdos-Renyi Graph

Let us have an Erdos-Renyi graph $\mathcal{G} = \mathcal{G}(n,p)$. For a subset of vertices $S$ we define the cut-size $c(S)$ as the number of edges $(u,v)$ such that $u \notin S$ and $v \in S$. Let ...
user avatar
-1 votes
1 answer
69 views

Network flow optimization, additional symmetry condition

Let $N=(V,E,s,t,c)$ be a network (defined as usual). The "Max-flow min-cut" theorem states that the max flow passing from the source $s$ to the sink $t$ is given by the minimal cut. https://...
user avatar
  • 1,187
2 votes
1 answer
184 views

Max-flow problem for networks with weighted vertices [closed]

Let us define a network to be a weighted and directed graph $G = (V,E)$ such that $w(e) \geq 0 \ \forall e \in E$ and $\exists u,v \in V $ such that $s$ is a source (no edges going into $s$), and $t$ ...
user avatar
  • 415
1 vote
1 answer
43 views

Maximum number of diverse interactions between sets within a closed network

I have multiple networks where the edges between the nodes need to be drawn in a way that satisfies the following characteristics: Network needs to be closed in the sense that each node needs to have ...
user avatar
  • 13
0 votes
1 answer
55 views

Possible connections between N sets of nodes.

If you have two sets of nodes with the same number of nodes each, the number of possible connections is given by the binomial coefficient "n choose 2". Is there a general formula for the ...
user avatar
  • 35
0 votes
2 answers
41 views

What does the 'maximum flow' in a network graph mean?

The maximum flow in a capacity-constrained network can be found by methods like Folk-Fulkerson. For example, in the graph below: Here, the maximum flow from S to T has been calculated to be 19. I ...
user avatar
  • 241
0 votes
0 answers
8 views

Apply 2-port network model to the solution

QuestionsAfter answering Part A, I'm kinda struggling to understand Part B & C questions, I've spent a fair few hours researching these on the internet but not able to find anything that is ...
user avatar
0 votes
0 answers
8 views

Is there a unit of a consensus speed in Multi-Agent System?

I have a question about a consensus speed of a Multi Agent System(MAS) in control engineering. A consensus speed is defined as the second smallest eigenvalue of a matrix called graph Laplacian L. And ...
user avatar
1 vote
1 answer
45 views

Finding the likelihood of 'at least 1 successful path' in a DAG

Our (software dev) team is working with a system that can be represented as a DAG with a starting node and an ending node. Our goal is to ensure a message can flow from the start vertex to the stop ...
user avatar
0 votes
0 answers
21 views

Adjacency Matrix of d-regular graph [duplicate]

"If 𝐴 is the adjacency matrix of a 𝑑-regular graph, then any row of 𝐴 contains exactly 𝑑 1’s. Thus, the vector 1𝑛=1,1,…,1 is an eigenvector of 𝐴 with eigenvalue 𝑑." How do we know ...
user avatar
1 vote
0 answers
25 views

Minimum degree of separation using ranking lists as edges

TL;DR: I want to find the minimum path from a node $X$ to a node $Y$ in a directed graph. But the edges aren't directly given: There are some rankings (ordered lists of nodes), and there is a directed ...
user avatar
  • 11
0 votes
0 answers
39 views

Sparse Graphs with a Small Maximum Cut

Let us have a connected graph $\mathcal{G}(V,E)$ where $V$ are the vertices and $E$ the edges. Define the maximum-cut as $M(\mathcal{G})$, which is a division of the vertices into two sets with a ...
user avatar
0 votes
0 answers
23 views

The smallest eigenvalues of the union of complete graphs

It can be checked that every adjacency matrix of the complete network on size n has the smallest eigenvalue -1. So, let A_{i}'s be adjacency matrices of complete networks with different sizes n_{i}. ...
user avatar
  • 1
1 vote
0 answers
48 views

What is the diameter $D$ of a square portion of square lattice, with $L$ nodes along each side, for a network of network size $N$?

What is the diameter $D$ of a square portion of square lattice, with $L$ nodes along each side, for a network of network size $N$? My understanding is that each edge has $L$ nodes, and the square of $...
user avatar
  • 11
0 votes
0 answers
57 views

Expected number of connections between different colour nodes in a network with variable connectivity

Background There is a network of $N$ nodes. Each node has a colour: Red; Green or Blue (in a more general form they may be additional colours, but there is at least one other colour that Red and Green)...
user avatar
1 vote
1 answer
31 views

T-Colouring of Hamiltonian Circuit in Cubic Graph

I am trying to understand this paper On Hamiltonian Circuits. I am unable to understand why the following is true : $ X( S_{1}) +X( S_{2}) +X( S_{3}) = 0.$ $\: (1)$ Here $X(S)$ is representing the $...
user avatar
0 votes
1 answer
47 views

What is the definition of betweenness centrality for weighted directed networks?

According to Wikipedia, the betweenness centrality of a node ${\displaystyle v}$ is given by the expression: $${\displaystyle g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$$ where ...
user avatar
  • 7,280
0 votes
0 answers
25 views

"Weak Links" in a "Small World" Network

I am trying to identify the Weak Links in a "Small World" type of network. A Small World network is multiple strongly connected clusters with sparse interconnections between the clusters. ...
user avatar
0 votes
0 answers
16 views

Open Source Tools for Graph Analytics

What are the best open-source (no code, GUI based) tools for visualizing and analyzing Network Data. I am currently using NodeXL and Giphy also looks interesting. Any other options?
user avatar
0 votes
1 answer
28 views

How to proof in the best way possible that this network has a min cut of finite capacity

I am trying to prove that the min cut of the following network is 900. From looking at it I think it is obvious. I think the problem lies in the fact I have some infinite capacities and will need to ...
user avatar
0 votes
0 answers
20 views

How to determine n-node connected subnetworks in a given directed graph?

For a given directed graph, I want to determine all 4-node connected subnetworks. Do we have any specific algorithm designed for this for calculating 4-node connected subnetworks?
user avatar
1 vote
0 answers
74 views

Switch size of a multiple binary-tree network

Description of a multiple binary-tree: A multiple binary-tree network has n inputs and n outputs, where n is a power of 2. Each input is connected to the root of a binary tree with n/2 leaves and ...
user avatar
  • 45

1
2 3 4 5
9