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
1
vote
0answers
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 ...
1
vote
1answer
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-...
0
votes
1answer
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. ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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$ ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
19 views

Common neighbour matrix of a graph

Problem Let $G = (V,E)$ be a simple graph, $A$ its adjacency matrix and let $c(u,v) = |N(u) \cap N(v)|$ be the number of common neighbours of any pair of nodes $u,v \in V$, i.e. $$c(u,v) = \big|\big\{...
0
votes
0answers
20 views

Optimization of a random walk

I'm working on a project related to random walks on a network, where the nodes are concepts/ideas/innovations, and the links between them denote the relationship between two ideas. The entire network ...
0
votes
0answers
9 views

Networks and Submodularity

I have no idea in proving a problem in graph theory. Let $G$ be a direct graph on vertex set $V(G)$ and edge set $E(G)$. Assume that $V(G)$ has a special "source vertex" $s$ and a special "sink vertex"...
2
votes
1answer
37 views

Are “bus” and “star” topologies homotopic?

All I know about topology is coming from Numberphile videos of Cliff Stoll (klein bottles, donuts...) and I am learning about network topology only because I'm an electrical engineering student; so I ...
1
vote
2answers
29 views

What do you call a graph with two nodes but no edge connecting two nodes?

I was studying about subgraph and I have question about it. So let's say there is a graph G which has two nodes, A and B, and an edge connecting node A and B. I learned that graph can be called by ...
0
votes
0answers
12 views

Similarity of Generated Path to Known Graph

Background I have graph, $G(V,E)$, that was constructed from a known a chemical reaction network. Each node $v \in V$ represents a specific molecule and each edge $e \in E$ represents a chemical ...
1
vote
0answers
74 views

What is this math symbol? [duplicate]

I am learning statistical network analysis and came across this symbol (highlighted in the screenshot below) that I do not know what it means.
0
votes
0answers
8 views

Network Analysis Proof: Degree distribution function is scale-invariant

I am reading the proof for the statement "Degree distribution function is scale-invariant/scale-free". The slides I am reading says: Let F(d)=proportion of nodes with degree at most d=$\mathbb{P}(...
1
vote
0answers
22 views

Percolation theory critical density simple proof!

Is there a simpler proof for the existence of infinite connected component in 2D lattice (percolation theory) if the probability of connection exceeds a critical threshold? Currently, I am reading the ...
3
votes
1answer
58 views

Would a grid-like graph have lower average shortest distances than a random graph?

Imagine two different types of street networks with the same number of nodes and where edges are weighted according to their length. Both network types cover the same geographic area (say 1 km²) and ...
1
vote
1answer
51 views

Deriving network modularity

My question is exactly what was asked here: Specifically: Given [this definition of $Q$] we proceed by writing $s$ as a linear combination of the normalised eigenvectors $u_i$ of $B$ so that $s = \...
1
vote
0answers
24 views

Calculating average path length of a varation of Newmann-Watts model!

This problem is from Networks: An Introduction by Newmann. Consider the following variation on the small-world model. Again we have a ring of n vertices in which each is connected to its c nearest ...
0
votes
0answers
26 views

How to quantify social network similarity/distance?

Context In the context of animal social networks analysis, I wish to compare two empirical sampling methods, M1 and M2, through simulations. Simulation workflow is as follow: I generate a ...
1
vote
0answers
19 views

Eigenvector equation in a similarity score of regular equivalence for networks

In Newman's book Networks, it is given a similarity measure for regular equivalence $\sigma$ (in page 198, 2nd edition and page 217, 1st edition) as a matrix defined by $\sigma = \alpha A \sigma A$,...
0
votes
1answer
36 views

How do you explain the unit of this formula?

I have trouble trying to interpret the following formula: $$G_{SCI} = \mu N^{span} G^3 \mathrm{arcsinh}\,(\rho \Delta f^2)$$ $$G_{SCI} = \frac{P_{SCI}}{B},$$ where $P_{SCI}$ is the self-channel ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
14 views

Notation on distribution over finite sets

I'm puzzled about the meaning of $\Delta S$ in the following statement: At each time period, $t \in N$ and conditional on the realization of state $\theta$, agent $i$ observes a private signal $\...
0
votes
0answers
15 views

Calculating network density in a hypergraph

Is it possible to calculate network density with a hypergraph? Network density is defined as the proportion of edges to the number of possible edges. Does this generalize to hypergraphs? If so, does ...
0
votes
0answers
17 views

Proving random walk on $Z^3$ is transient using network theory

I am looking at Example 21.9 in Page 295 here which uses flows of electrical network theory to show that $Z^3$ is transient and I have a couple of questions about the proof. Proof: To each directed ...
0
votes
2answers
58 views

Effective Resistance of two joined Vertices

Let $G=(E,V)$ be a connected Graph with $V \subset \mathbb{Z}^n$ Am I right with my assumption that if $(x,y) \in E$ meaning x and y are connected with an edge $e$ with the conductance $c(e)$. Then ...
0
votes
0answers
30 views

Finding path-network such that each connected component contains certain points

So I'm currently working on a geometric optimization problem and came upon a graph-problem where I am struggling to find a solution. Edit: So let $\{x_i\} \subset \mathbb{R}^2$ and $\{y_j\} \subset \...
0
votes
0answers
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)?
0
votes
1answer
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 ...
5
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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?
1
vote
0answers
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 𝐱̃ ...
3
votes
1answer
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 ...
0
votes
0answers
12 views

Survey of models for generating networks

I have been reading about models used for describing real-world networks that are used in network science. Examples include the well-known Erdos-Renyi, block-stochastic model, Barabasi-Albert, ...
2
votes
2answers
19 views

Does order matter when dealing with networks?

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-...

1
2 3 4 5
7