The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
67 views

Optimal allocation in network

Given a network (N,g). We want to analyse specializaton matters. Nodes are individuals, and they can product goods and services just like in our usual economy. Individuals can be consumers too. This ...
0
votes
0answers
6 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? ...
0
votes
0answers
12 views

How do you sure the effect of seeds in a viral marketing campaign don't overlap .

If you have the ability to infect several several nodes, how do you make sure the infection caused by a seed does not overlap with an others. For example if seed 1 infects nodes 1,2 and 3 and seed 2 ...
0
votes
1answer
18 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
10 views

Why are dynamic networks probabilistic?

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
19 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
0answers
19 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
16 views

Graph Theory Help, Assortativity Coefficient with Weighted Edges. Remaining weights vs. Total weights. (undirected graph)

a combo network analysis and igraph/r question. It is cross posted with stackoverflow (and I will hopefully not be laughed away). I am trying to find the assortativity coefficient for an undirected ...
0
votes
0answers
13 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
10 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
0answers
30 views

Computer Networks - Queues (Check my math)

A buffer is filled over a single input channel and emptied by a single channel with a capacity of 64 kbps. Measurements are taken in the steady state for this system with the following results: ...
0
votes
1answer
29 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
0answers
22 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
16 views

Inflow and outflow of Traffic graphs

For my bachelor thesis I am making a model for calculating a distribution of traffic in a network/graph given the delay on the links of the graph. I have written a Matlab program, and it seems to ...
0
votes
0answers
21 views

mathematics related to switching theory

This questions is related to the application of mathematics in switching theory. I am trying to understand the number of layers of switching required for a very big networks. In the literature they ...
0
votes
0answers
47 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
43 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
47 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
22 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 ...
0
votes
0answers
13 views

Calculating the Estrada Centrality

The Estrada centrality of a node i is given by $E_i =(e^A)_{ii}$ where $A$ is an adjacency matrix Express the Estrada centrality in terms of the number of loops of length r $N^r_{ii}=[A^n]_{ii}$ ...
0
votes
1answer
27 views

Perceptrons that recognize AND, OR, NOT

I'm trying to figure out how to create a set of perceptron weights: one for AND, one for OR, one for NOT. I'm not sure where to begin, but any hints are greatly appreciated!
1
vote
0answers
24 views

Is modularity of -1 possible

Wikipedia mentions that modularity of a network is within the range [-1,1).But if we consider a complete graph with n nodes and assign different community to each node than the modularity turns out to ...
0
votes
0answers
70 views

Calculate optimal path through changing network?

Apologies if this question is not suited for this forum. The question extends beyond my knowledge of mathematics and programming, it is quite hard to get my head around it let alone put it in to ...
0
votes
0answers
28 views

Intuition behind spectral radius of a graph

Suppose that I have a graph G, along with its respective adjacency matrix A. The definition of how one can compute the spectral radius of this graph is not hard to grasp, but I was wondering about the ...
1
vote
1answer
41 views

Deriving the probability of a node (vertex) on the end of a random chosen link (edge) having degree d.

From Jackson - Social and Economic Networks p. 87 (link: http://press.princeton.edu/chapters/s4_8767.pdf p.12 in pdf): (...) (T)he distribution of degrees of a node found by choosing a link ...
0
votes
0answers
66 views

m/m/1 Queuing Theory - Average Delay/Utilization Graph confusion

I'm currently coding a single server single queue m/m/1 simulation with Lambda as arrival events rate (Poisson) Omega as service rate (Exponential) and I'm having problem understanding how to ...
0
votes
1answer
31 views

Generate random graph under centrality constraints

Is it possible to generate a random graph under centrality constraints? I am currently working on a project involving characterization of biological properties stemming from different centrality ...
1
vote
0answers
42 views

Evidence propagation in bayesian network

I'm currently trying to wrap my head around evidence propagation in bayesian network (simple tree propagation) but I'm having trouble finding information about the process. As an example, let's take ...
0
votes
0answers
22 views

Sampling with/without order

Our professor have presented this simple example in the lecture. You have $P_n$ processors and $M_k$ memory where $k>n$. If two or more requests goes to same memory then the request will be ...
0
votes
1answer
35 views

Attractors of a Random Boolean Network?

I need some direction on the topic of Random boolean networks (NK-boolean networks or Kauffman automata). I now some of the results like if K=1 the systems settles down to fixed points, if K=2 it ...
4
votes
2answers
144 views

Number of elements in cartesian power with a majority constraint

Problem: I would like to know the number of elements in the cartesian power $X^n$ (cartesian product of one set $X$ by itself, $n$ times) with a majority constraint: how many elements in $X^n$ have a ...
0
votes
0answers
26 views

$k$-core vs $k$-component?

Can someone tell me what the differences between $k$-core and $k$-components are? Base on what I understand: $k$-core: each vertex connects to at least $k$ others in the subset $k$-component: each ...
3
votes
0answers
81 views

Transpose of the adjacency matrix

As homework I had to do an adjacency matrix for the following graph: My solution was the following: $$ \begin{bmatrix} 0&0&1&0&0 \\ 1&0&0&1&0 \\ ...
0
votes
0answers
57 views

Why the space of all permutations of a vector (n!) is smaller than the space of all possible permutations of a sorting network?

Imagine you have a vector with 2048 entries. The total permutations are 2048! Now you have a sorting network let us say AKS, the total number of possible results with nlog(n) gates is $2^ {n log (n)}$ ...
0
votes
1answer
35 views

Can a comparison network obtain all the n! permutations of a vector?

I want to permute a vector using comparison networks. This is the only method I have at my disposal. My original idea is to use a sorting network like Batcher or Bitonic. Basically I place my vector ...
1
vote
0answers
124 views

Are there any programs like family echo that I can use to map mathematics?

Family echo is an online program that allows one to make a family tree, if nothing is clicked it shows most of the family tree as it is, but if one clicks a name one can see clearly all the ancestors ...
1
vote
0answers
28 views

Choosing which sets of nodes are 'top' and 'bottom' in bipartite graph representations of real-world complex networks.

A bipartite graph is a triplet $G=(\top, \bot, E)$ where $\top$ is the set of top nodes and $\bot$ is the set of bottom nodes, and $E\subseteq\top\times\bot$ is the set of edges. Often real-world ...
0
votes
1answer
34 views

A question about Bayesian Networks from Judea Pearl's book.

"Given a probability distribution $P(x_1, \dots, x_n)$ and any ordering d of the variables, the DAG(directed acyclic graph) created by designating as parents of $X_i$ any minimal set П$_{X_i}$ of ...
8
votes
1answer
641 views

Powers of adjacency matrix doesn't seem to correspond to observed number of paths on graph

I would really appreciate some help on this! $A^n$ represents $n^{th}$ power of the adjacency matrix of a graph. I keep reading that the $A^n_{ij}$ entry equals "the number of paths of length n ...
0
votes
0answers
28 views

Finding P(S1 = 1 | D1=1, D2=1) (Bayes Networks)

I'm scratching my head over something that is probably simple Probabilities, but I guess I can't see it. Essentially, I have the following table: ------ ------ ------ ------ | D1 | D2 | S1=1 | ...
0
votes
0answers
18 views

How to find giant(largest) component list at network data

If i have a network data as below 1 2 1 3 1 4 2 3 2 5 3 6 .. .. 1st column is node number and 2nd is too. and 1st and 2nd node are connected. (that is network datas) then we can find ...
1
vote
0answers
34 views

are graphs/networks additive

I was wondering if networks/graphs are the sum of their parts. Let's say you have a 15-node network. The spectral density of that network has X kurtosis and Y skewness. You also have a 20-node ...
0
votes
1answer
32 views

Measure for presence of several poorly interconnected components in undirected graph

Is there a measure to classify networks regarding whether or not they are composed of several (internally closely connected) groups which are poorly connected (i.e. few links between groups). That ...
0
votes
1answer
22 views

Scale free networks (power law)

I'm working with a dataset, of which I'm analysing the degree distribution. I'm finding that it obeys the famous power law/scale free degree distribution $\propto k^{-\gamma}$, but the value of ...
0
votes
0answers
46 views

Algorithm for creating a directed scale free network with a fixed amount of nodes

I'm trying to figure out an algorithm that produces a scale free, directed network, for which I can give the final amount of nodes as an input. Now, this is a little bit tricky for a few reasons, so ...
0
votes
0answers
20 views

what is the name or class of such graphs: the probability that two nodes are connected is decided a function of the distance

Random geometric graph is: Randomly place N nodes in a topologic space, if the distance between two nodes is smaller than a specific value, then these two nodes are connected. Now, slightly ...
0
votes
0answers
13 views

correlations between network parameters

I am calculating spectral densities for networks. Is there a reason why skewness and kurtosis would, in general, be correlated across many networks? That is, as a feature of networks rather than ...
0
votes
1answer
49 views

Bayesian Network vs Markov Decision Process

I am wondering if somebody can tell me anything about the practical differences between using Markov Decision Processes and and Bayesian Networks in reasoning about probabilistic processes?
0
votes
0answers
56 views

Techniques & Algorithms used to solve Shorted Hamilton Path, Hamilton Circuit Questions

I'm interested in knowing different techniques in approaching the following: Shortest Hamilton Path, Hamilton Circuit (when weights have been given for each edge) Hamilton Circuit - Current method ...
0
votes
1answer
19 views

partily undirected Bayesian Network

I am designing a Dynamic Bayesian Network, but I am a little confused about some definition of DBN and markov network. In my network ,the edges from the hidden nodes of last frame to the current frame ...