All Questions
Tagged with network-theory graph-theory
17 questions
1
vote
0
answers
50
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
0
votes
1
answer
237
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
0
votes
1
answer
54
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
0
votes
1
answer
58
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,503
7
votes
1
answer
306
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,561
1
vote
0
answers
50
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
0
votes
1
answer
872
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
3
votes
1
answer
586
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
1
vote
1
answer
102
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
6
votes
2
answers
301
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
12
votes
1
answer
542
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
0
answers
30
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
4
votes
1
answer
158
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,871
2
votes
1
answer
5k
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 ...
- 123
2
votes
1
answer
92
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
1
answer
212
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
0
answers
60
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 ...
- 41.8k