# Questions tagged [network]

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

322 questions
Filter by
Sorted by
Tagged with
15 views

### Stochastic Block Models regimes and topology

Hi I'm trying to understand how regimes and thresholds of Erdős–Rényi model are valid in symmetric stochastic block model. In Erdős–Rényi model $G(n,p)$ each edge is drawn independently with ...
15 views

### Ways to obtain networks from multivariate time-series

I recently became aware of a bridge between (dynamical) properties of time-series and (topological) features of an associated network representation. A variety of methods exist to embed the time-...
28 views

### MLE for an undirected network degree distribution

I have an empirical undirected network. I assume, that a degree distribution is $F(k) = 1 - e^{1 - \frac{k}{m}}$. and would like to estimate $m$. The only method I'm aware of for such task is MLE. ...
40 views

### Solving the integral with norm vector over bounded region

I have to solve an integral like this: $$d = \iint\limits_R{||x||^{-2/3} dA}$$ And the problem I have is described like this: *there is a disk region R having an area of 100 m² and in this ...
16 views

### Probability that a node loses an edge in the Barabási-Albert (BA) model with removal of edges

I'm following the book Networks by Mark Newman. He considers an extension to the BA model where edges are removed uniformly at random. He computes the probability that a particular node $i$ loses an ...
12 views

### Size of the set T in a T-join problem

I am an undergraduate that is taking a course in combinatorial optimization and I have come onto studying T-join problem. Could someone please explain why the size of the set $|T|$ has to be even in a ...
17 views

### Ford-Fulkerson for maximum cardinality matchings

If I have a bipartite graph $G(V_1 \cup V_2)$ and I wanted to find the maximum matching. Why is it that the ford-fulkerson algorithm will take at most $min{(|V_1|,|V_2|)}$ iterations? I know that in ...
16 views

### Generating function exponential random graphs with expected number of edges ⟨m⟩

We refers to Statistical mechanics of networks by Park and Newman in the section. Random graphs Considering exponential random graphs with fixed number of vertices n we know only the expected ...
37 views

### Edge probability and expected number of edges in the configuration model

This question is related to question: Probability that exists at least an edge in the configuration model There is something I do not understand about the computation of the expected number of edges ...
56 views

### Voltage difference in electrical network

Suppose we have an electrical network consisting of $n$ nodes and the graph is connected. Let $a$ and $b$ be two of the nodes. Now we put an external source at the network such that the voltage at $a$ ...
23 views

### Express three-factor product in matrix form

For a small project of mine, I would like to model a phenomenon (impact of mood and opinion on a social network's member). The data I have is stored in square, same-sized matrices. I would like to ...
12 views

### Adjacency spectra of a graph interpretation

I'm not a mathematician and I have a question about spectral graph theory. Is it possible to conclude that we have a fully connected network, if an adjacency spectra of a graph is continuous with no ...
27 views

### Newman algorithm yielding different result to what is given in his paper

Summary I am trying to implement Newman's algorithm for community detection, outlined in this paper. I am testing my implementation against one of the datasets used in that paper to benchmark the ...
15 views

### Average path length in random DAG

Suppose I have a random directed acyclic graph (DAG). By random I mean that edges are drawn uniformly at random so that the adjacency matrix is lower triangular with i.i.d. entries. Is there any ...
8 views

### matrix notation for the cost function of neural networks

large thick letters stand for matrices optimization problem: $\min\limits_{\mathbf{K},\mathbf{W},b}E(\underbrace{\mathbf{W}\sigma(\mathbf{KY}+b)}_{=: \mathbf{C}},\mathbf{C}^{obs})$ is this Notation ...
20 views

### Divisibilty Graph and Eigenvector Centrality

The Divisibility Graph is constructed as follows. Let the vertex set V be the finite set of first n natural numbers {1,2, ...n}. Draw an edge between i and j if i divides j. This graph is an ...
14 views

### Sum over pairs of nodes forming a triangle

Given a simple graph $G=(V, E)$ and a matrix, $C$, describing a property for each pair of nodes, e.g., the adjacency matrix, or the matrix describing the number of common triangles of two nodes. Is it ...
19 views

15 views

### betweenness centrality of $G$

Consider an undirected graph $G$ (of $m+n+1$ nodes and $m+n$ edges) where a node $v$ is connnected to two different trees $T_m \& T_n$ rooted at nodes $a \& b$ respectively. Thus nodes $a$ and ...
15 views

### Finding effect of inputs on output (shapely values)

I've developed a neural network which takes in n inputs returning m outputs. I want to see which inputs contribute most with each output. One idea I had is for all inputs/output combinations, lock ...
14 views

9 views

### Node attribute inference

Are there some heuristics for node attribute inferencing similar to that of link prediction heuristics (e.g. Adamic & Adar, Common Neighbor, Katz centrality etc)?
27 views

### What centrality measure can be used to rank important nodes relative to a particular node in a knowledge graph?

Given a knowledge graph $K$ and a particular node in it called $N$, I want to find out the set of nodes that are important related to the node $N$ only. I started looking up some papers and the ...
78 views

### Can I use graph theory to prove this is the optimal way to connect dots?

I'm working on a project related to making broadband available in rural areas. As part of this project, I'm looking at the shortest distances between connected properties and those that are not ...
69 views

### Proving a bipartite graph is not planar

I have drawn the bipartite graph K3,3. And I need to prove this graph isn't planar. I used contradiction, assuming it was planar, using Eulers formula to prove it wasn't planar. I concluded my graph ...
136 views

### Confusion about the definition of an acyclic graph

My textbook says Definition 1: A graph, G, is acyclic if it contains no undirected cycles (otherwise it’s cyclic). It also says Definition 2: A (directed) cycle is a (directed) path which ...
33 views

### Creating a directed scale-free block model

I am trying to created a directed scale-free graph which is divided into few blocks. In the case of Stochastic Block Model we can define the probabilities of connection between nodes associated with ...
44 views

### Graph theory induction

Prove by induction that if $G$ is a complete graph, which has n vertices, then the network $G$ has $n(n − 1)/2$ edges. How do we go about induction with networks?
72 views

### PageRank sensitive calculation

𝐀 is the adj. matrix of a directed graph 𝐺. 𝐱 is the PageRank vector we calculate for a given 𝛼 (e.g. 0.85). 𝐶 is a subset of pages of 𝐺, for which we change some of the outgoing links. By 𝐱̃ ...
339 views

### How to calculate this weighted adjacency matrix?

In "Higher-order organization of complex networks", network motifs is used to transform directed graph into weighted graph so that we can get symmetric adjacency matrix. Here's how it works. There're ...
I have a question regarding networks, I just recently started studying graph theory, and I was wondering for this network below can I say that a path connecting $B$ and $H$ is B-A-C-D-G-H or B-A-F-E-...