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

1
vote
0answers
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 ...
5
votes
2answers
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: ...
0
votes
0answers
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 ...
1
vote
0answers
16 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
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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: ...
17
votes
3answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
0answers
47 views
1
vote
1answer
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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, ...
0
votes
0answers
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 ...
2
votes
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
37 views

Markov Process w/ a non-stochastic matrix?

I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum ...
0
votes
0answers
49 views

Decomposing the non-deterministic transition functions in non-Markov decision processes into several deterministic transition functions

Problems in reinforcement learning are commonly modeled as Markov decision processes (MDPs). One essential part of MDPs is the transition function $T: S \times A \times S \rightarrow [0, 1] \in ...
3
votes
1answer
153 views

What is the difference between graphs/networks? [closed]

Note: read down to below "Question" to find the question. Background: In a previous question I asked how to group what I would call nodes on a network graph based on a connectivity matrix. (link) ...
3
votes
0answers
42 views

Generating column stochastic random matrix with target row sums

I want to populate a 0-1 matrix, which is an adjacency matrix, corresponding to a directed graph, with weights on the elements that are 1. In other words, I want to generate an $N\times N$ matrix $A$ ...
0
votes
1answer
17 views

Any way to exploit relations between examples in dataset?

Suppose I have a dataset with k examples: id1, feature1, feature2 .. featuren ... idk, feature1, feature2 .. featuren For which I cat mark a training set and feed ...
0
votes
0answers
65 views

Determining k in k-means clustering by community detection in graph

I am faced with a problem of choosing an appropriate number of clusters in highly dimensional data. I've read many approaches to determine the number of clusters, and finally came to a solution and I ...
0
votes
0answers
44 views

Graph generation model effect on performance of Spectral graph algorithms

I use spectral graph algorithms for finding community structures, specifically the Leading Eigenvector Method (http://arxiv.org/abs/physics/0605087). I try analyzing the performance of these ...
1
vote
1answer
158 views

techniques for sampling graphs? (possibly implemented in r packages)

Let's say I have a very large graph that proves impractical for visualization ends and I wanted to sample a random subgraph. (I know that I can filter out a subgraph via measures like degree, ...
0
votes
0answers
8 views

The authenticity of the N-cut measure when the number of components in the data is high

I'm running a clustering task on unlabeled data, and assume we're validating our results by applying the Min-Cut measure as an internal validity index. Let's refer the normalized version of the ...
0
votes
0answers
18 views

is a network the sum of its subnetworks?

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
0answers
21 views

Understanding the shape of networks' laplacian spectra

We often see normalized Laplacian spectra of graphs (networks) where density on eigenvalue 1 serves as an axis of symmetry, with particularly high (blue spectra in the figure) or low densities (red ...
0
votes
1answer
85 views

Correlated random draws with graph structured correlation

I have a problem where I have a graph structure, such that some nodes are connected to other nodes i.e. we have an adjacency matrix of size n*n with a 1 corresponding to a connection and 0 otherwise. ...
2
votes
1answer
22 views

Where can I find tutorials about graph theoretical regression

Hi I am a biology graduate currently working on a problem that requires me to use Graph theoretical regression model. While I have taken a couple of applied regression model courses. I don't have much ...
0
votes
1answer
37 views

Bayes nets - calculating probabilities

Given a Bayesian network, say a -> b -> c, all binary random variables (I won't show the CPTs, assume they are given). You are told b and c are true. How do you calculate the P(a=True)?
3
votes
3answers
148 views

Probability that node A is connected to another node

Example: I have nodes A, B and C. A is connected to B and C. B is also connected to C. The link between two nodes have a probability to fail. For the link between A and B, the probability is pAB ...
0
votes
0answers
34 views

Merging two disconnected graphs

Firstly, I'd like to apologize for any misused terms or ways I could have made the description much more succinct. It's been a while since I took machine learning during my bachelor's. I have two ...
1
vote
1answer
31 views

Given a graph, identify users more likely to connect to a new user

I have some twitter-like data described as tuples of users (u1, u2), that means u1 follows u2. I also have a second dataset with another list of tuples (r1, r2), that means user r1 frequently click on ...
1
vote
0answers
34 views

Is Social Network Analysis or NER the best way to create a semantic graph?

I am planning to create a semantic graph by creating an automatic ontology. I want to know which is the best process to do it. Doing social network analysis to create people, relationships, likes, ...
1
vote
0answers
19 views

Representing graph as a n dimensional binary vector

The author in this paper http://www.di.ens.fr/~shervashidze/papers/SISO08lrgc.pdf, on pg 2, first para, top left the author states that In graph classification the goal is to learn a decision ...
0
votes
1answer
12 views

Identify search strategy over network

Imagine a website. Each page is a vector, each hyperlink an edge. Many people connect to this website. I collect the pages visited and the links clicked. The data-set is made up of all these "paths" ...
0
votes
0answers
12 views

Why do chordal graphs not lose conditional independences when its transformed from undirected to directed to factor graphs and around?

When chordal graphs are used to model probability distributions, why is it that they do not lose conditional independences when its transformed from a undirected to a directed to a factor graph and ...
0
votes
0answers
45 views

How to reconstruct a small world network adjacency matrix corrupted with noise

I have an adjacency matrix which corresponds to small world network. However, all the elements are small and it is corrupted with noise (with positive value) that stems from multiple sources, and ...
2
votes
0answers
55 views

Efficient algorithm to enumerate all member DAGs of a Markov equivalence class

I'm working on a research project involving Bayesian networks. BNs are directed acyclic graphs (DAGs) used to compactly represent joint distributions of variables. In many cases, multiple DAGs can ...
1
vote
1answer
33 views

Matrix reordering algorithms

I have a similarity matrix and I would like to apply an algorithm that reorders the entries based on their similarity. The aim is to move entries with high similarity closer to the main diagonal. The ...
0
votes
0answers
25 views

Expectation of ratio of functions of Bernoullis: a concentration question

Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$, and let ...