The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
13 views

What series describes the feedback of a fully connected network with signal strength at each node converging to 1?

Take a fully connected network with $N$ nodes operating in lockstep. One and only one node will receive a signal from an external source at a time step $t$, but the node receiving it is random. The ...
1
vote
0answers
44 views

Representing distances in high-dimensional space

I have a set of n points $P_i$ $(i=1..n)$ in an d-dimensional space. I can calculate the distances of every point to each other point. What is the best way to represent the distances of these ...
0
votes
0answers
13 views

Clustering Coefficient of A Transitive Graph/Network

Whats the difference of a transitive network's clustering coefficient and a non-transitive networks coefficient? more precisely is the clustering coefficient of a transitive network is as high as ...
0
votes
0answers
12 views

Katz centrality and Node removal

I'm looking for any results about how Katz centrality changes when a given node is removed from a graph. For instance, if I define a function to be the average of the Katz centrality of the remaining ...
0
votes
1answer
37 views

Are minimum cut communities maximal?

I am looking at the paper Graph Clustering and Minimum Cut Trees by Flake et al. Let $G(V, E)$ be some undirected weighted graph. Definition. Let $s, t\in V$ be given. Let $(S, T)$ be the minimum ...
0
votes
0answers
7 views

Dominance Network Worded Problems

What are some methods to solve this? Normally for dominance I do as such: Write a matrix for one step dominance, then find total dominance by = D+D^2 - then sum each row of the matrix. Using this ...
0
votes
1answer
23 views

Problem Solving - Project Crashing Time

My working out: (EST,EFT) times for the activities: A: (0,0) B: (0,8) C: (3,3) D: (10,38) E: (10,18) F: (18,18) G: (25,33) H: (58,58) I: (25,33) J: (45,53) K: (118,118) Finish: (133,133) ...
0
votes
1answer
44 views

Algorithm for finding contradictions in a directed graph that represents implications

I need an algorithm that does this: For a directed graph where nodes represent boolean values and edges represent implication (implies TRUE and implies FALSE): If (arc exists between any ...
0
votes
0answers
13 views

Maximum Local Clustering Coefficient of any graph?

I am currently reading a programming book that shows a few graph analysis things, one of which is the local clustering coefficient of a graph that the author is working with. Then he has an example ...
1
vote
1answer
43 views

Average path length: can't figure out the meaning of $\large\frac{1}{n(n - 1)}$

I am doing a few tests with the Average Path Length formula. I am testing with a directed acyclic graph. I am generating all the shortest path using a breath first walk. Everything works fine. ...
0
votes
0answers
18 views

Successive shortest path with infite distances

I have some error in reasoning while trying to understand the successive shortest path algorithm as described in Ahuja, Magnanti, Orlin "Network flows". The algorithm starts with the zero flow and ...
0
votes
0answers
12 views

(Alternative) Notation for set of successors of a vertex in a directed graph

I am looking for the standard notation for the set of successors/predecessors of a vertex of a directed graph. I have seen $N^{+}(v)$ and $N^{-}(v)$ used to represent the set of direct successors and ...
0
votes
0answers
18 views

Resizing Edge Weights Bases on Node Sizes

I am new to graph theory and I and trying to create edge weights based on the sizes of the connecting nodes. My problem in particular is as such: I have a directed graph of e-mails that were sent ...
0
votes
3answers
22 views

Equivalence Graphs

On the basis of this definition: Two graphs are equivalent if they have the same set of edges (ex. (A,B),(A,C)) how would you determine equivalence for graphs that are not labelled: ex.
1
vote
0answers
35 views

Queueing Delay(W) for M/D/1 queue with different value of service times

I have a problem of calculate the queueing delay of M/D/1 queue. There are two different types of packets with different size. Such that, the arrival rate $\lambda$ and service times $\mu$ will not be ...
1
vote
0answers
8 views

Giant component of a network

Let v be the number of nodes that are not in the giant component. Then, u = v/n is the fraction of nodes that are not in the giant component. If a node is in the giant component, its k neighbors are ...
0
votes
1answer
123 views

network structure — k-cliques vs p-cliques

In network structure, what is the difference between k-cliques and p-cliques, can anyone give a brief explaination with examples? Thanks in advanced! ============================ EDIT: I found an ...
0
votes
0answers
36 views

How to calculate least moves of fruit.

I have a question, I'll try to abstract from the real problem to not lose people. What I'm really looking for is the name of the algorithm or class of problem to find my solution. I feel that this is ...
5
votes
0answers
80 views

Probability of transmission between two nodes in a neural network at exactly d timesteps

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired the ...
2
votes
2answers
80 views

Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
0
votes
0answers
25 views

Prove a problem about Networks(in graph theory)

$S$ and $T$ are two subsets of $V(N)$, which is the set of vertices in network N. Let $S^c$ denotes the complement of $S$ and $[S,S^c]$ be the set of arcs starting in $S$ and finishing in $S^c$. If ...
0
votes
2answers
25 views

complex networks

I am just a bit curious about the following question. Following wiki, the definition of "complex networks" goes as follows: " Most social, biological, and technological networks display substantial ...
0
votes
1answer
57 views

what is difference between open and mixed queue

please consider this image: In this picture that I got it from Here write said that Network C is Open,B is Mixed and A is Closed. I want to know why C isn't mixed? ...
2
votes
1answer
24 views

what is and how to generate a Net representation for a given polyhedron?

The so called Net representation for a Tetrahedron is depicted in the following image ( link to wolfram ) : What is this for ? How to reason about this and how to generate this very same ...
0
votes
0answers
14 views

What is the implication of seeing a power law in real data?

I am studying a course named Networks. It is a question left in the lecture. Given a network, we define the degree distribution by $$ p_k:=\frac{\#\{\text{nodes of degree }k\}}{\#\{\text{number of ...
1
vote
0answers
24 views

Formulating an Equation for the sum of some functions

I am trying to calculate the sum of percentages of some groups: the network is composed of groups of networks, each group is composed of nodes, I am calculating the percentage of few nodes in the ...
0
votes
1answer
14 views

Mean number of FFL subgraphs with one output node

So, this is a Feed Forward Loop. It is a regularly occurring subgraph of a huge random graph. In the case of X,Y,Z being any nodes, we have that the mean number of times that a subgraph G appears is ...
0
votes
0answers
18 views

How to realize the simplest agreement protocol

Consider the simplest case: 1 o-----o 2 with x1 = 1 and x2 = 11 The agreement protocol is: I think we can realize it by the discrete case: In this ...
0
votes
1answer
29 views

Expected number of directed links in a network

Suppose we have a network with n nodes, in which every directed link exists with probability p (independent from each other). What would be the expected number of directed links if we express them in ...
0
votes
0answers
24 views

probability in graphs - degree distribution

I am reading this paper on networks which employs probability in analyzing graphs. Suppose that a graph has $n$ vertices. Furthermore, if each vertex has a probability $p_k$ of having $k$ neighbors, ...
1
vote
1answer
56 views

Probability that exists at least an edge in the configuration model

In this period, I am studying some topics on random networks to understand the modularity optimization used in community detection. In particular, I am trying to understand a model called ...
0
votes
0answers
22 views

Multiple Attachment to the Same Node in Barabasi-Albert Model

In the Barabasi-Albert Model, is a newly introduced node allowed to attach more than once to the same node? The master equation does not seem to include terms describing nodes gaining more than one ...
0
votes
2answers
126 views

Real world application of dominating set?

can anyone tell me about the application of vertex coloring problem and algorithm for vertex color problem in graph or networks.
0
votes
1answer
23 views

Return list of k-paths in a network

Consider a network $ G(V,E) $ with vertex set $V$ and number of edges $E$ being formed by a pre-defined formation process, with one edge being placed in each step. Now, a k-path is defined as $(i,j) ...
0
votes
0answers
20 views

Bayesian Network understanding

I am confused by the definition of Bayesian Network. It's well know that graph $G$ of Bayesian Network can be viewed in two very different ways: As a data structure that provides the skeleton for ...
0
votes
0answers
34 views

Graph theory Centrality

I am trying to work out centrality in a network using Freeman's network centrality. I have an in degree of 83 and an out degree of 110. I want to work out the network centrality using my out degree ...
1
vote
0answers
49 views

Probability that the network is connected in an unstructured p2p network

Suppose that three nodes form an unstructured p2p network (a network where each node has a list of neighbors node, in which there are addresses of c live neighbors) and each selects to cache the IP ...
0
votes
0answers
20 views

Echo State Network learning Mackey-Glass function, but how?

I got this example of a minimal Echo State Network (ESN) which I analyse while trying to understand Echo State Networks. Unfortunately I have some problems understanding why this really works. It all ...
0
votes
1answer
60 views

Can a graph have the same number of strongly connected components and weakly connected components?

Exactly what the title says. Can a graph have the same number of strongly connected components and weakly connected components? I am using networkX and have the same number for a dataset for both ...
0
votes
0answers
47 views

Expected assortativity coefficient of random graphs

I am wondering whether there exist a closed-form expression for the expected assortativity coefficient (http://arxiv.org/pdf/cond-mat/0205405.pdf) of an Erdos Ranyi random graph model $G(n,m)$, where ...
1
vote
1answer
128 views

Rate of packet arrival

Channel has bit error probability p. Number of bits in packet is Poisson distributed with mean lambda. How do I calculate the rate of successful packet arrival? This is what I have done so far: Assume ...
0
votes
0answers
24 views

How would game theorists solve the DARPA Network Challenge

What would be a correct game-theory-based solution for DARPA Network Challenge, which was won by setting 1/2-1/4-1/8-... incentive scheme for the network of participants?
2
votes
1answer
85 views

Usefulness of eigenvalue centrality

Question for the network theorists/computer scientists: I heard that the eigenvalue centrality is "useless" and "too sensitive to jump behavior" for directed graphs. $\bullet$ What does this mean ...
1
vote
0answers
28 views

Jackson network, steady state

My question is below: Consider a network of n queues with a Poisson arrival process of parameter t from outside the network, and independent exponentially distributed service times of ...
0
votes
0answers
27 views

Network component detection

Suppose I have a (directed) graph with nonnegative edge weights. I would like to separate the graph into what you might call "$\epsilon$-components", that is, a partition $\{ V_i \}$ of the set $V$ of ...
1
vote
1answer
538 views

Proof of König's theorem

Let $G=(V,E)$ be a graph. $H\subseteq V$ is called a vertex cover of $G$ iff $(u,v)\in E\Rightarrow u\in H\vee v\in H$. Now let's assume $G$ is bipartite, i.e. $V=V_1 \cup V_2$ and $E\subseteq ...
5
votes
2answers
191 views

Are resistor-battery networks always uniquely solvable?

Note: if you know the basics of circuits, feel free to skip the brief background; the question is at the bottom, starting below the triple horizontal rule. Most people with some physics background ...
1
vote
1answer
223 views

What is additive homomorphic encryption and multiplicative homomorphic encryption? [closed]

Explain in brief about additive homomorphic encryption and multiplicative homomorphic encryption. I have read about them but I could not properly understand. So would you please elaborate additive ...
0
votes
1answer
37 views

Find out the probability of a path break for an eight-hop path given that the probability of a link break is p?

Can we apply Binomial distribution here? How do I approach it? How the method will change when topology change from linear to ring topology?
0
votes
1answer
47 views

The Dons Problem: Minimizing the time for complete diffusion of information [duplicate]

A friend of mine asked me this question recently. He might have heard from somewhere else, but that's the extent of my background on this problem. It might have a completely different name, and I ...