Graph theory is a branch of discrete mathematics that studies graphs. Graphs are representations of sets of objects & their interrelations, where the objects are 'nodes' and the connections amongst them are 'edges'.

learn more… | top users | synonyms

0
votes
0answers
7 views

Difference between adversarial, random and stochastic ordering in data streams

Kindly explain the difference between adversarial, random and stochastic ordering in data streams in layman terms
0
votes
1answer
27 views

maximal subset - include nonuniform node weights and node values

I am trying to solve a graph theory problem. I have an undirected graph where the nodes have node weights n and edges have edge weights g. I want to be able to select the subgraph such that the ...
3
votes
1answer
35 views

Probability of at least one triangle in Erdos-Renyi graph

This is a well-known problem in random graph theory, where we show that if $X$ is the number of triangles in $G(V,E,p)$ with $p=o(\frac{1}{n})$, we can show that $$ P(X \geq 1) \geq 1-o(\frac{1}{n}) ...
0
votes
1answer
20 views

igraph shortest path export as vector [closed]

This is probably a very simple question but I cannot seem to solve it: I'm using the igraph package and want to export the vpath part of the get.shortest.paths output as a vector so that I may work ...
1
vote
0answers
50 views

Correct way of computing Shannon Entropy of a walk

Take for example a walk such as: ["school", "work", "home", "kindergarten", "home", "school", ...] # or simply [1, 2, 3, 4, 3, 1, ...] What's the correct way of ...
0
votes
0answers
13 views

How to make educated guess about movement of people through graph?

I have data about weekly counts of people on entry points (orange circles on the picture below) and need to make educated guess about their counts at destination points (marked by green stars). I know ...
3
votes
0answers
18 views

Is there an estimate for the variance of average minimum path length for Erdős–Rényi graphs?

I am calculating the average minimum path length of Erdős–Rényi graphs. I am using the $G(N,n)$ model whereby a $N$ node graph with $n$ edges are generated uniformly. I found the expected average ...
0
votes
0answers
7 views

Maximum vocabulary distance

Given a vocabulary with size m (the number of letters in it) and words of length n, what is the maximum word distance (number of differing letters) for a text with length o (the number of words in ...
1
vote
1answer
40 views

Vulnerability index for every node of graph

Given a particular undirected graph with n nodes, is there an index that would characterize the vulnerability of each of the nodes? By vulnerability I mean the susceptibility of the graph to ...
0
votes
0answers
10 views

Ways to summarize the number of users and messages sent as a comparative quantity?

I have a dataset where there are different groups of users, and the number of users in each group are different. They each send out messages to members in their own group and other groups. Eg. 3 users ...
1
vote
0answers
19 views

Information entropy in a direct graph?

I have a directed graph, and each edge in the graph has a probability, representing certainty in the edge. How can I represent overall uncertainty in the network. I was thinking of using an ...
0
votes
0answers
17 views

Got an entropy-ish function for a multinomial distribution? Graph theory and Bayes net related

I have a discrete variable $X$ that can take on one of three states; $a$, $b$, and $c$. Thus it has two parameters $p_a = P(X = a)$ and $p_b = P(X = b)$, of course $P(X = c) = 1 - p_a - p_b$. I am ...
3
votes
0answers
26 views

Combining bipartite graph with one mode graph

I have a director-firm bipartite graph. In addition, I have a kinship relationship graph which includes the directors. I would like to combine the two adjacency matrices, but that violates the basic ...
0
votes
0answers
11 views

Looking for algorithm that is a discounted min-cost-maximum-flow calculation

In terms of graph theory I am very familiar with minimum-cost maximum flow, connectivity and ...
0
votes
0answers
19 views

Is Pearson correlation on graphs a valid approach to compare undirected weighted graphs?

I have came to several instances where researchers use Pearson correlation to compare edges of two graphs to find out if they are similar. For example, given two symmetric adjacency (proximity) ...
2
votes
1answer
52 views

are there any alternatives to graph theory?

I was planning to use a graph theory / page-rank approach to find the most influential person in an organization. Influential person is someone who drives a lot of activity in the ...
0
votes
0answers
25 views

Conditional independence representation in graphs

My question is related to the second part of this question here below in this url regarding conditional independence and its graphical representation Assuming we consider an example ...
1
vote
0answers
12 views

Cluster into communities a graph with negative edge weights representing repulsion [duplicate]

Consider an undirected graph $g$ with some edges having negative weight - all weights in $[-1,1]$. We are seeking communities or clusters. Negative edge weight means repulsion and positive means ...
2
votes
1answer
37 views

Probabilities in markov graphs

I have a first order markov graph which looks like Now I was told if we make B an absorbing state(NULL) the graph simplifies to I was also told that the conversion probability is 1 in the first ...
4
votes
0answers
139 views

Multiple eigenvectors in graph spectral clustering

In Newman's PNAS 2006 paper Modularity and community structure in networks, the first eigenvector splits the graph in two clusters, and then each cluster can be further divided by eigenvector of a ...
3
votes
0answers
51 views

Theoretical link between the graph diffusion/heat kernel and spectral clustering

The graph diffusion kernel of a Graph is the exponential of its Laplacian $\exp(-\beta L)$ (or a similar expression depending on how you define the kernel). If you have labels on some vertices, you ...
1
vote
0answers
36 views

Comparing two graphs/markov chains by comparing their clusters

I have an undirected graph representation of my system (a dynamical system), i.e. I have some labelled nodes and bi-directional edge weights, so everything is in a Markov matrix form. Now I can form ...
3
votes
2answers
119 views

Statistical Test for “clumpiness” of graph

My data set is a list of items and for each item a list of all other items that this item has cooccurred with. Effectively this is an adjacency matrix for a non-directed graph. I'm looking for some ...
1
vote
0answers
54 views

Bayesian link prediction problem: advice to deal with unfamiliar likelihood

Imagine that we have a graph $G$ such as the one in the figure and that we take a snapshot of this network every day. Our hypothesis is that the probability that node $i$ will have at least one new ...
5
votes
3answers
246 views

Graph clustering algorithms which consider negative weights

I have a graph instance with weighted directed edges which values can be in range [-1,1]. I need to do clustering on this graph, in order to find out groups in which vertices are more correlated. I ...
1
vote
0answers
41 views

Modeling a Classification Problem with an Undirected Graphical Model

I have an undirected graphical model problem which I'm looking for some help on. So, the goal is to perform multivariate classification: based on a set of observations, I want to predict the correct ...
1
vote
0answers
22 views

dynamic rooted tree graph

Suppose I have a tree graph rooted at point P1, if I moved this point (P1) to another place in the tree, can I change the data structure by changing the points IDs so that the graph still rooted at P1 ...
1
vote
1answer
33 views

How can I solve this graphical model?

I have a classification problem, with the following structure. There is a fully-connected graph, and each node needs be assigned a class label. Every pair of nodes in the graph has a probability ...
0
votes
1answer
34 views

Validating Personalized Pagerank Matrix computation in R

My question is with reference to this paper here This is an excerpt from the paper From the similarity of the two equations we can see that if ppr_alpha_u is added up it will be equal to pr_alpha ...
0
votes
0answers
22 views

Computing and validating personalised PageRank in R

I have been trying to calculate personalized pagerank matrix in R however I am facing some logical issues. As described by the paper by Archak et al found here, in section 5.2 the sum of the column i ...
0
votes
0answers
34 views

Small Point Set Matching

I'm trying to match two small sets of points (~10 each) and can't find a particularly successful algorithm. All points have a known co-variance matrix and are only 2D. Many points in each set are ...
1
vote
1answer
383 views

Calculating Personalized PageRank in R

Is there anyway I can calculate the personalized PageRank in R? A little bit about Personalized PageRank The Personalized PageRank matrix is defi ned as a n by n matrix solution of the following ...
2
votes
1answer
156 views

How to test statistically whether my network (graph) is a “small-world” network or not?

A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps. ...
0
votes
0answers
17 views

Comparing two graphs and calculate probability they come from the same source

I'm looking at data related to people badging in and out of a plant. I know where and when a person uses their badge to gain access. What I'd like to do is take a certain amount of data for an ...
1
vote
0answers
84 views

Model for supervised learning on graphs with varying structure

Colorization problem is considered. I have a training set of unordered graphs (images) with varying number of vertices and edges (color regions and adjacency between them, resp.). A fixed number ...
3
votes
0answers
119 views

Highly Connected Subgraphs cluster

i'm studying a method to cluster similar topic represented in a graph like this: The result must be: [0] = 1,2,4 [1] = 3 I tried Markov Cluster Algorithm but ...
0
votes
1answer
117 views

Should I use IN or OUT degree in Network Diffusion Model of Twitter network using iGraph?

I'm trying to run Independent Cascade Model for my Twitter graph to see who I have to stimulate to get the maximum cascade. This code is inspired by ...
6
votes
1answer
83 views

What methods exist for tuning graph kernel SVM hyperparameters?

I have some data that exist on a graph $G=(V,E)$. The vertices belong to one of two classes $y_i\in\{-1,1\}$, and I'm interested in training an SVM to distinguish between the two classes. One ...
0
votes
0answers
30 views

How to get to closest estimation of betweenness in large graph network using igraph?

I have a quite large graph of twitter followers. After importing, I have around 2 million nodes and 6 million edges. ...
1
vote
0answers
20 views

The definition and the role of cliques in Markov random fields

I'm freshing up on machine learning (specifically image analysis) and of course looked into Markov random fields. I really cannot wrap my head around the concept of cliques and their application in ...
8
votes
3answers
177 views

Statistical model to predict the next move on network only using movement history

Is it possible to build a statistical model that predicts the next move in a graph solely based on past movements and the structure of the graph? I have made an example to illustrate the problem: ...
0
votes
0answers
44 views

Graph Edit Distance - strings versus matrix-->vector conversion?

I have two adjacency matrices and I want to find the graph edit distance between them. The only implementations I'm seeing (I need this fast) is edit distances in MATLAB (sigh...) for strings. I have ...
1
vote
0answers
38 views

Comparing adjacency matrices

I have 25 weighted adjacency matrices which can be potentially translate into 25 networks. I want to see how ``similar'' are the resulting networks (in a graph theory sense). Is there a way to do ...
1
vote
0answers
69 views

Is there an alternative to PCA that produces a unique representation?

PCA produces solutions that are not unique i.e. the resulting representation could be recreated using a different set of points. This is where my problem lies. I was wondering whether anyone is aware ...
1
vote
2answers
250 views

How are graphs of k-nearest neighbors built? (for clustering)

I’ve seen that there are several clustering algorithms (for example, CHAMELEON or even Spectral Clustering) that work by converting the data into a weighted (or sometimes unweighted) k-nearest ...
0
votes
0answers
103 views

Tying scale free network generation to the power law distribution

I am trying to understand how the link between the Barabasi-Albert graph generation and the scale-free networks it generates. Specifically, what is the mathematical relationship between the ...
0
votes
0answers
29 views

How to construct 3D image from 2D image using Markov Random Field?

I have one 2D CT image and I want to convert it to 3D image using Markov Random Field. There are several papers in the literature in which this technique was used based on 3 2D orthogonal images. ...
0
votes
0answers
136 views

Fit power law to degree distribution data

I try to use poweRlaw package to fit a power law to degree distribution data. The minimal reproducible example goes as follows: ...
18
votes
3answers
741 views

Where's the graph theory in graphical models?

Introductions to graphical models describe them as "... a marriage between graph theory and probability theory." I get the probability theory part but I have trouble understanding where exactly graph ...
0
votes
0answers
14 views

Connecting vertices in a graph stochastically. How to calculate a joint condition?

Full disclosure: I've posted this on reddit at /r/askstatistics, but haven't gotten any feedback yet, so I'm re-posting here in the hopes of getting some more exposure. Sorry for the long question. I ...