# Questions tagged [network-theory]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
1 vote
39 views

### Bounds on the spectral radius of a perturbed directed graph

Suppose $(G_n)$ is a sequence of strongly connected directed graphs (without multiple edges) with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be ...
• 11
42 views

### An $n$-dimensional generalized Hoffman’s circulation theorem?

For a directed graph $G$, a 1-dimensional circulation is a function $f:E(G)\rightarrow \mathbb{R}$ such that for every $v\in V(G)$, $$\sum_{uv\in E(G)}f(uv)=\sum_{vw\in E(G)}f(vw),$$ where $uv$ is an ...
• 251
1 vote
27 views

### Both-way flows in a directed graph

Let $G$ be a finite directed graph, and let $s,t$ be two distinct vertices. Problem $1(s,t)$. Find the maximum number of mutually edge-disjoint directed paths from $s$ to $t$. OK, I didn't think of ...
• 36.9k
93 views

### Graph alignment by considering 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'...
• 101
40 views

### Properties of preferential attachment such as spectral gap

Short question: Is there a good math reference on the properties of preferential attachment graphs? In particular, expansion properties seem to interest me. More details: I try to investigate the ...
• 947
47 views

### Minimum spanning tree and projection

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) ...
• 47
24 views

### Epidemic risk models on graphs with fuzzy edges

I am reading the paper mentioned above, but I have some questions because I have some confusions. image Questions What is the motivation behind transforming the original formula in the network model? ...
143 views

### Impact of the global cost function (weighting) to Betweenness Centrality distribution

I have a graph whose edges have all a weight of 1. In my particular case computing the Betweenness centrality by counting shortest paths between all pairs results ...
53 views

### Does the Lawrence–Krammer representation provide a quantized action on the space of networks?

Let $\rho:B_n \rightarrow H_2(\overline{C_2 P_n})$ denote the Lawrence–Krammer representation of the braid group on $n$ symbols. The group $H_2(\overline{C_2 P_n})$ is a free $\mathbb{Z}[q,t]$-module ...
53 views

### integer network flow with symmetry

Suppose we have a weighted directed graph $G=(V,E,f)$. Each $e\in E$ is associated with $f_e\in \mathbb{N}$. There is a source node $s$, which only has outgoing edges, and a sink node $t$, which only ...
• 1,471
211 views

### Real world applications of graph limits

It is well known that the area of graph limits (initiated by Lovász and coauthors) had provided a very powerful framework to deal with problems arising, for instance, in extremal combinatorics and ...
• 1,483
251 views

### What are the right mathematical tools / language to analyse complex networks over time?

In this article about human physiology as a complex network the authors say that: "Lacking adequate analytic tools and a theoretical framework to probe interactions within and among diverse ...
• 2,102
1 vote
47 views

### Is a function of a centrality measure a centrality measure?

I have been trying to wrap my head around the following question. Suppose you a have a centrality measure for a weighted, undirected network. Let's call the calculated centralities with $\pmb{x}>0$....
• 31
48 views

### Correlation of centrality measure random vectors [closed]

Let's assume that we have 2 random vectors A=(a1,a2,a3) and B=(b1,b2,b3). Each of these elements is a centrality measure of a network. For instance a1 and b1 are the centrality measures of the same ...
• 109
552 views

### Centrality measures in a network with negative correlations

I have a bidirectional network where the weights of edges are based on partial correlation matrix. I have both positive and negative values as weights. Now, I want to compute centrality measures as ...
• 109
1 vote
68 views

### Is there a theory for forcing "sludge" through a network, analogous to electric current flows?

I'm familiar with the correspondence between reversible Markov chains, random walks, and electric current flows, as described in Probability on Trees and Networks by Lyons and Peres. Is there an ...
• 33
431 views

### Small world network regime

I have recently read Watts, D., Strogatz, S., Collective dynamics of ‘small-world’ networks, Nature 393 (1998) pp. 440–442, doi:10.1038/30918, on small-world networks, and is still not very clear to ...
• 33
111 views

### Sources of information on algorithms for finding Hamiltonian cycles (Pósa)

I research various algorithms in complex networks and I am quite new in this field. I am currently focusing on random geometric graphs - Pósa's algorithm for finding a hamiltonian cycle. Can you ...
1 vote
99 views

### How do I fit flow values to connections in a known network?

This is not my area and I'm new to its terminology, and am posting my problem in the hope that someone will be able to direct me to where it has been solved, or who has written about it. I have a flow ...
• 11
291 views

### Searching for an early, highly theoretical, even philosophical, math paper on models or small-world networks

All I can remember is that it was very high-level / abstact and kind of philosophical, explaining (the discovery or interdependence of) small world networks. I assume that it was +50 years old and '...
• 103
506 views

### Distribution of degree in graphs: when is the friendship paradox the paradox it wants to be?

$\DeclareMathOperator\deg{deg}\DeclareMathOperator\ndeg{ndeg}\newcommand\abs[1]{\lvert#1\rvert}$The friendship paradox goes most people have fewer friends than their friends have on average. The ...
• 343
1 vote
236 views

### total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
• 383
1 vote
28 views

### Number and different kinds of spnning trees in a weighted graph

We know that for a unweighted graph the number $\tau(\mathcal{G})$ of unique spanning trees of $\mathcal{G}$ is $$\tau(\mathcal{G})=\det L_\mathcal{G}^{\{n-1\}},$$ where $L_\mathcal{G}^{\{n-1\}}$ is ...
• 345
141 views

### Almost all simple graphs are small world networks

Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution ...
• 3,777
4k views

### Adjacency definition for a directed graph

For an undirected graph, we know that nodes are adjacent to each other if there is a link that connects them. What about adjacency for directed graphs? Is it based on: outgoing links: node $n$ is ...
58 views

### Transversal deviation in first passage percolation

Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic ...
• 612
84 views

### Literature on the controllability of networks under attack

I would like to request your advice on a problem arising from my research in the life sciences. Consider a modular, sparse weighted network which is partially controllable in the sense that some ...
• 21
1 vote
187 views

### Number of sequences of edges that contain at least one subsequence which is a walk between vertex $i$ and $j$

Typically a walk is defined as a vertex-edge sequence, e.g. $(v_1, e_1, v_2, e_2, v_3)$, but suppose we are working in the undirected simple graph setting. Instead, let's say an edge-sequence \$(e_1, ...
• 220
1 vote