The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
22 views

Network energy function matrix representation

The question seems very simple, however I`m trying to find the right blas-function which correctly describes the following expression: $\sum_{i=1}^{N}\sum_{j=1}^{N}{w_{ij}x_ix_j}$ Is it ...
0
votes
0answers
7 views

Normalization of the log-Betweenness Centrality

In the paper I'm reading, the author refers to the betweenness centrality of a node with respect to another node, X. They then go on to define the 'node performance' as the normalized value of the ...
0
votes
0answers
11 views

Why is a “scale-free” network defined as one whose degree distribution obeys a power law?

Aren't these two different concepts? I think "scale-free" refers to the fact that the degree distribution doesn't depend on the size of the network. So wouldn't a network with degree distribution ...
-1
votes
0answers
23 views

Average number of connected triples in a random graph G(n,p)

I need to prove that the expected number of connected triples in a random graph $G(n,p)$ is $\frac{1}{2}nc^2$ when the average degree is $c$. I know that $c = (n-1) p$. I also figured out that if you ...
0
votes
0answers
17 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. ...
0
votes
0answers
15 views

Condition for global cascade

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 ...
1
vote
0answers
10 views

What are some centrality measures that don't satisfy “star maximization?”

Some have proposed that for a natural centrality measure, the most central a node can get is the center node in the star network. I've heard this called "star maximization." That is, for a measure ...
0
votes
0answers
17 views

The modularity formula of Newmann and Girvan

I have question concerning the modularity formula of Michelle Girvan and Mark Newman. It says that it measures the fraction of edges in a network, that connects nodes, within the same ...
0
votes
0answers
12 views

Two variants of Radiality centrality

I am implementing Radiality centrality. For formula I am using definition from CentiScaPe: Network centralities for Cytoscape. I was doing some tests and I found some examples at Wolfram Alpha site. ...
0
votes
0answers
27 views

Power law networks exercise

I'm studying the power law networks (scale free) and I try to so this exercise from by book (Albert Barabasi - Linked): The degree distribution $p_k$ expresses the probability that a randomly ...
0
votes
0answers
4 views

What is a compact graph/network in Graph theory (discrete mathematics)

I've searched this definition but in everyplace I juts had find the topological definition that is compact if it is finite, but I remember it is something aboth its conections, thanks
0
votes
0answers
22 views

Algorithm for dtecting negative edge cycle and then remove cycle which have odd number of negative edges

can anyone suggest me that how to remove negative edge which are involve into create a negative cycle? for exam ...
2
votes
0answers
31 views

What measures of centrality exist for fully connected networks with weighted directed edges?

I have a network of cities with transport links between them. The transport links are not symmetric in both directions, therefore asymmetric edges between nodes. There is a variable number quantifying ...
1
vote
0answers
13 views

are there any other properties like sub-modularity which can help compute the maximization problem of a set function

Now I have a set function $f$ (it's monotone), which inputs a node set $S$, and output a real value $r=f(S)$. And I want to compute $$ \max_{S,|S|\leq k}f(S). $$ where k is given number. And I know ...
1
vote
2answers
45 views

Probability $u, v$ are connected in a random graph model

There is a random graph problem. Given an undirected graph $G(V,E)$ associated with $p_{uv}$ to denote the probability there is an edge between $u$ and $v$ ($p_{uv}$ are independent, maybe different ...
4
votes
0answers
126 views

Network contagion

Suppose I have an undirected, unweighted network in which some node, $i$, is infected. This (and any) infected node has probability $p$ of infecting adjacent nodes. Is there a closed form expression ...
0
votes
0answers
15 views

incidence matrix of weighted directed graph

How is the incidence matrix of a weighted directed graph defined? By def, the incidence matrix $ M = (m_{ij}) $ is $n$ times $m$ matrix where $n$ is number of vertices and $m$ is number of edges. ...
0
votes
0answers
22 views

Travelling Salesperson MTZ

I have been solving a $10$ city travelling salesperson problem. Having solved the assignment based relaxation problem, I have $5$ subtours: $1 \rightarrow 10 \rightarrow 1$ $2 \rightarrow 8 ...
0
votes
0answers
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 ...
0
votes
0answers
8 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 ...
1
vote
0answers
31 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 ...
1
vote
0answers
23 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 ...
2
votes
1answer
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 ...
0
votes
0answers
27 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 ...
0
votes
0answers
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 ...
0
votes
0answers
22 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 ...
0
votes
0answers
64 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. ...
0
votes
1answer
64 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 ...
4
votes
2answers
139 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 ...
1
vote
3answers
35 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 ...
0
votes
0answers
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 ...
1
vote
0answers
22 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 ...
0
votes
1answer
44 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 ...
0
votes
1answer
68 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 ...
2
votes
1answer
75 views

How to estimate the conditional probability of node reachability on a random graph?

Let $G=(V,E)$ be an undirected random graph such that $V$ is the node set, $E$ is the edge set. Each edge $uv \in E$ is associated with a probability $p_{uv}$, i.e., $uv$ is kept with probability ...
1
vote
0answers
25 views

Optimization formulation for a dynamic system. Constructing constraints for a problem.

I am trying to formulate a problem that goes the following Min $f(.)$ This is a generalized objective function. Subject to, $x_{i}^{(t+1)} = x_{i}^{(t)} + r_{i}^{(t)} - x_{i}^{(t)}z_{i}^{(t)}$ ...
1
vote
0answers
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. ...
0
votes
0answers
30 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? ...
1
vote
2answers
37 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? ...
0
votes
1answer
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 ...
2
votes
0answers
53 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 ...
1
vote
1answer
226 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 ...
0
votes
0answers
24 views

Marginal distribution of degrees of connected node pairs

I got this equation from Module 6CCMCS02/7CCMCS02, Theory of complex networks, compact lecture notes, from King's college London. This is the marginal distribution of connected node pairs in a ...
0
votes
0answers
29 views

Initialization of Network Simplex with known flows

I am trying to figure out how to initialize the network simplex algorithm when you know the flows you want to start with. And I am interested solely in bipartite graphs (partition of nodes in sinks ...
0
votes
1answer
182 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 ...
1
vote
2answers
62 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 ...
0
votes
0answers
97 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 ...
1
vote
1answer
74 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? ...
1
vote
0answers
132 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 ...
1
vote
0answers
29 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...