The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
27 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
17 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
8 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
23 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
20 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
36 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
20 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
21 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
41 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
21 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
34 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
21 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
17 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
137 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
21 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
48 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
55 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
69 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
23 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
29 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 ...
6
votes
1answer
342 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
16 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
33 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
25 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
15 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
28 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
18 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
11 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
37 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
37 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
17 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 ...
2
votes
0answers
27 views

median eigenvalue

When I look at the spectral density plots of my (usual) laplacian graphs, they spike at the median eigenvalue. But what significance for the graph/matrix (which originates from a network) does the ...
0
votes
0answers
28 views

Prove a complex function to be convex

I have a function and want to prove that it is convex when $0 \leq x \leq 1$: \begin{equation} f(x)=\frac{b1g'(x) f_1(x)^{n-2}+g'(1) \gamma}{g'(1) ( \gamma+b1) } \end{equation} and \begin{equation} ...
1
vote
1answer
75 views

Second-price sealed-bid auction uniformly independent with unknown value

a disclaimer before the question: this is a homework problem. I just want some help/push in the right direction, I'm kind of stuck! The problem is as follows: In a second-price sealed-bid auction for ...
0
votes
0answers
32 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
50 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
34 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
20 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
52 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
33 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
83 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
53 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
27 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
67 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
32 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
16 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 ...
1
vote
3answers
170 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
68 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 ...