Tagged Questions

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'.

11 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 ...
75 views
+100

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: ...
10 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 ...
16 views

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 ...
43 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 ...
58 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 ...
19 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 ...
11 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. ...
31 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: ...
609 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 ...
10 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 ...
7 views

State of art algorithms to triangulate a moral graph and find maximal clique

I am currently working on an application of triangulation on a given moral graph and then finding the maximal cliques. So, I would like to know any well written papers and the state of art algorithms ...
8 views

Is there a statistical test that allow to see how much of one subgraph is supported by another subgraph within the same graph?

For instance I am interested in the packet routing through the internet. I am interested by a specific subtype of packets routed between a set of points A and set of points B. This set of routes ...
47 views

What's the difference between a Markov Random Field and a Conditional Random Field?

If I fix the values of the observed nodes of an MRF, does it become a CRF?
39 views

How does one map a graph into a feature space?

Assuming there is an undirected weighted graph. How can one convey it's geometrical structure into a feature space? Are there any common practices?
11 views

Matching two same sized graphs

What methods would one use to match two weighted, complete graphs with the same number of nodes? Node labels are identical and the matrix can be sorted. I would tend to simply use normalized ...
12 views

Is SEM appropriate for this problem?

I want to estimate some latent variables but I'm not 100% sure that Structural Equation Modelling is the correct way to do it, or if there are any easier solutions. I have a pretty basic graph <50 ...
55 views

How can I infer the value of multiple dependent continuous random variables in conjunction with discriminative learners?

I have 2 continuous random variables V1, V2 which are dependent. I want to infer each of their values based on: The value of ...
55 views

Probability of relations in a network

Imagine, i have a random graph with $n$ nodes representing people. Between every two nodes there is an edge representing friendship with probability $p_2$. These edges are independently generated, so ...
84 views

Comparing undirected weighted graphs

I want to get a sense of the similarity between weighted, undirected graphs. My data are from an EEG experiment, where every vertex is an electrode, and every edge is the connectivity between two ...
12 views

Similarity of linear subgraphs

I have a directed graph, on which I have a number of linear subgraphs. In the simple example graph below, these subgraph might be a->b->c->e->g->h, ...
25 views

Ranking search results

I was looking at npm (the largest javascript package manager) and how they implemented the search results ranking. Each package has several important fields: name keywords description ...
60 views

Law of the Seven Degrees of Separation [closed]

I would like to know whether any empirical studies have been conducted on the so-called "Law of the Seven Degrees of Separation", a statement that any two people in the world are separated by at most ...
68 views

Finding natural groups / clusters in an undirected graph / over several undirected graphs

What kind of methods are there to find natural groups or clusters within an undirected graph structure? I am new to graph theory, but the project seems to have confronted me with questions that could ...
50 views

Is this a valid method for unipartite projection of a bipartite graph?

I would like to know if a given method of projecting a bipartite graph exists, and if yes, if there is a formula for transforming the weight matrix. Given a bipartite graph with edges' weights ...