Questions tagged [network-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
19 views

Correlation of centrality measure random vectors

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 ...
0
votes
1answer
53 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 ...
1
vote
0answers
60 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 ...
3
votes
1answer
150 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 ...
0
votes
1answer
71 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
1answer
75 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 ...
6
votes
2answers
271 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 '...
12
votes
1answer
414 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 ...
1
vote
0answers
130 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 ...
1
vote
0answers
23 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 ...
4
votes
1answer
127 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 ...
1
vote
1answer
1k 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 ...
2
votes
0answers
43 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 ...
2
votes
1answer
79 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 ...
1
vote
1answer
91 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, ...
1
vote
0answers
50 views

On the defect of a flow network

This problem in graph theory was actually motivated by some problems in Theory of Fractals. To formulate the problem I need to recall some definitions related to flow network. A flow network is a ...