# Tagged Questions

The tag has no usage guidance.

24 views

19 views

### Creating a closed parent-child network structure

I am new to this forum, and I am hoping that there is a mathematical solution to this situation. I am trying to form a network structure of parent and children nodes, but with some conditions. ...
15 views

Assume a unidirectional, unweighted network generated according to a degree distribution. Each node is given a value between 0 and 1 called threshold $\phi$. We topple some nodes, the neighbours will ...
11 views

8 views

### Graph Theory: What is the best kind of network centrality to use to determine flows? sources/sinks?

I am working on a medium-sized (80 vertices), cyclic, directed network with commodities being passed around between agents. Its actually stock market data. I would like to determine who of the ...
9 views

### Freeman's Network Centrality

I'm going through some lecture notes on a lecture I missed and I'm struggling to come up with the answer for these three graphs. What I know: N is the number of nodes D is the max degree ...
43 views

### Graph with super nodes where each super node may have one or more sub-nodes in it

I have a question related to a problem I'm working on currently which is related to graph theory and complete sub-graph of size k (clique of size k). Let us say we have a graph where each node has one ...
26 views

### Why is the eigenvector centrality considered a generalized version of degree centrality?

The eigenvector centrality of a vertex in a graph, is a self-referential centrality, which basically says that a vertex with a high value of eigenvector centrality is one that is adjacent to highly ...
26 views

### Is there a term in mathematics for Metcalfe's Law?

Metcalfe's Law states that the value of a network is proportionate to the square of the number of users. This comes from the idea that there are $N*(N-1)/2$ pairs in a network of size $N$. Does this ...
28 views

### Rate of Change of a Sum

Disclaimer: Probably stupid question Is there a polynomial representation of the rate of change with respect to $n$ of $$f(n)=2n-3+\sum_{m=0}^{n-3}{(n-3-m)}$$ and if so, how can I find it? (For those ...
10 views

### Graph optimization with constraints

I have a graph and I need to visit each and every node $n_i$ in the graph starting from a node of choice. There is a cost of not visiting a node, which is different for different nodes, $c_i$ and the ...
24 views

### Show that the feasible flow problem has a feasible solution if and only if for every subset S $\subseteq$ N, b(S) - u[S,S'] $\leq$ 0.

Show that the feasible flow problem, discussed in Application 6.1 below, has a feasible solution if and only if for every subset S $\subseteq$ N, b(S) - u[S,S'] $\leq$ 0. App 6.1: The feasible flow ...
69 views

### Hungarian Method algorithm question. Dual solution.

I have included two images which I have to prove the next problem. The first image is the alternate(k) algorithm (alternate paths algorithm) and the second is the Hungarian Method algorithm. Question:...
72 views

### Expected degree of a vertex in a random network

In the paper "Finding and evaluating community structure in networks" by M. E. J. Newman and M. Girvan section 5a, when they construct random communities as a network, they state: Edges were ...
149 views

### Textbook on Graph Theory using Linear Algebra

Is there any undergraduate textbook on graph theory using linear algebra? A request is a beginning with graph matrices that explain most concepts in graph theory? P.s. This thread has more specific ...
39 views

### The eigenvalues of $A=E-I$, where $E$ is a square matrix made up entirely of $1$'s and where $I$ is the appropriate identity matrix.

Let $A=E-I$, where $E$ is a square matrix made up entirely of $1$'s and where $I$ is the appropriate identity matrix. The following regarding $A$ is stated in my notes, but I am not sure how to show ...
20 views

### Proving the transitivity of a clustering coefficient

I am taking an upper level special topics course on Network Science at my university. Every class, we are given team-exercise questions which we are meant to work on with partners towards the end of ...
23 views

### Books/Notes on Synchronization in Dynamical Systems + Networks?

I am interested in references on Synchronization in Dynamical Systems, if possible from a Network perspective. Unfortunately I am an outsider to the field of Dynamical Systems and am not sure how to ...
46 views

### Space as a network. Is it possible to model topological properties of Euclidean (or non-Euclidean) space using a discrete network of points?

I've read Wolfram's book 'A New Kind of Science', which was very interesting and introduced me to the topic of cellular automata. But he also introduces the idea to model the physical space by a ...
77 views

### Intuition behind eigenvector centrality and computation procedure

There are various metrics that are used in social network analysis to estimate/find the influence of a node. Among them are various "centralities" - betweenness centrality, closeness centrality and ...
79 views

94 views

### Optimal allocation in network

We want to analyse specialization matters in a given network (N,g). Nodes represent individuals that can produce goods and services (just like in our usual economy) and that can be consumers too. ...
32 views

### Complexity of the Dinic, Malhotra, Kumar and Maheshwari (DMKM) method

I'm asked to prove that the complexity of the DMKM method is $\mathcal{O}(m\cdot n^{\frac23})$ if all capacities in a network are equal to 1. I have no clue where to start, can anyone give me a hint?
41 views

### What are dynamic networks.

From my understanding, dynamic networks are similar to traditional models except that they function in continuous time and have edges and nodes that evolve over time? Is this a correct understanding? ...
16 views

### Why are dynamic networks probabilistic? [duplicate]

I have a only survey level background in network science but am interested in it. I was browsing wikipedia and read this page, (https://en.wikipedia.org/wiki/Dynamic_network_analysis.) In that ...
56 views

### Possible Paths in Pipe Network

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit i have to ...
240 views

### Show that splitting an edge in a flow network yields an equivalent network.

Need help with this question from my Intro to Algorithms book: Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge \$...
186 views

### Degree distribution of the line graph of an Erdös-Rényi random graph

An Erdös-Rényi random graph is a graph, which consists of N nodes and where each link between them is present with probability p. It comes natural then that the pdf giving the probability of a node in ...
70 views

### Network theory and football?

I was reading the latest post on Azimuth, Network Theory in Turin, and I watched many of the lectures Baez posted on his site here. This might be a crazy question to ask considering it's not ...
108 views

### Bond percolation probability on a Bethe lattice

I derived the bond-percolation probability for a Bethe lattice and my result disagrees with a seemingly reputable reference by Albert & Barabasi (see below). I would be happy if somebody could ...
75 views

### Triangles incident to a node i

I'm trying to use some fragment-based measures for a network. Given an adjacency matrix representing a (large) network how do you calculate the number of triangles that are incident to every node i? ...
155 views

### Is there a method to measure the similarity between undirected graph vertices?

I'm doing some research on User Identity Resolution. Assume i can get two undirected graphs of a person, one is the friendship in Twitter of that person, the other ...