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
1answer
16 views

Does there exist an algorithm/package in R that tells if a matrix is aperiodic? [on hold]

I am currently reading Golub and Jacksons paper "Naïve learning in social networks and the wisdom of crowds" published in the American Economic Journal: Microeconomics in 2010. On page 120 they say ...
5
votes
1answer
47 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
41 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

Split graph into non-overlapping cliques [migrated]

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows: Every subgraph must be a complete graph/clique No vertex can be part of two or more ...
0
votes
0answers
11 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
15 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
58 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
36 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
27 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
29 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
38 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
136 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
29 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
16 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
45 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
43 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
84 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
7 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
16 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
15 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
65 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
21 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
35 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
130 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
28 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
29 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
27 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
25 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
44 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
26 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
20 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 ...
0
votes
1answer
33 views

Assessing Significance of Graph Statistics for a Selection of Vertices in a Network

I am dealing with the following problem: Assume $G(V,E)$ being an underlying network and $M_1$, $M_2$ sets of disjoint subsets of $V$ (e.g. if $|M_1| = k$, $M_1 = \{U_1,U_2,\dots,U_k\}$, ...
2
votes
0answers
43 views

Graphing the usage of legal precedents

I would like to hear recommendations on what tools to use to graph the usage of precedents in a legal court in Brazil. The data is searchable at www.stj.jus.br/SCON/, and in the most recent collegiate ...
0
votes
1answer
82 views

Centrality Measures for a directed multigraph

I have a directed multigraph that is used to represent an online discussion forum, where each actor is able to contribute comments to a discussion and have their comments commented on by other actors. ...
0
votes
0answers
49 views

Clustering method that can use graph links, discrete and continuous properties?

I have an un-weighted, directed graph that clusters ok using MCL or other graph clustering algorithms. However, I also have additional discrete and continuous properties of the nodes being clustered ...
0
votes
1answer
59 views

Clustering Two Variables With Disease Information

I was proposed a problem and I am not quite sure how to go about it. The problem is I want to find a relationship between two variables. For the simplified case there are only two variables, lets say ...
1
vote
1answer
60 views

Clustering a completely interconnected graph with weighted edges

I was wondering if Markov Clustering is what I really am looking for or not. Basically I have a N node graph in which every node is directly connected with one another. However, all the edges are ...
2
votes
0answers
206 views

Plot directed acyclic graph with scaled edge length

I am trying to design a network (more precisely a directed acyclic graph) with specific edge lengths. The data is on the form of an edge list, and for each edge, there is an associated length. It ...
1
vote
0answers
23 views

Bootstrapping a MST in R

I have a data matrix on GDP growth for particular countries for a particular period of time. From this matrix I get the correlation matrix. After that I use a nonlinear tranformation to obtain a ...
0
votes
0answers
63 views

Clustering coefficient for a clique

I would like to understand how to solve this exercise about clustering coefficient for a clique. As shown in the picture below if node pairs (a; b), (a; c), (a; d), (b; c), (b; d) are linked, then the ...
2
votes
1answer
123 views

Can Someone Explain How Factor Multiplication Works with Factor Graphs?

I'm taking the Probablistic Graphical Model course here: https://class.coursera.org/pgm-003/ This class uses the concept of Factors extensively with regards to graphical models: ...
3
votes
1answer
280 views

Financial exposures modelling with graph theory tools

I was wondering how finance folks go about storing and modelling portfolio exposure relationships with the aim to later aggregate or slice & dice the exposures by different factor sets. For ...
0
votes
1answer
25 views

Mining cycles from graphs

Suppose $T$ is a set of transactions containing some paths taken from a set of undirected graphs $G$ whose nodes are all taken from the same finite alphabet $A$. I would now like to extract all ...
4
votes
3answers
66 views

$\phi$-divergence?

I am frustrated of looking for a simple explanation of this term $\phi$-divergence, but I cannot find any. Therefore I would be really grateful if somebody could introduce a reference or write a ...
3
votes
2answers
57 views

Identifying middlemen in a social network

I have a data set and I want to examine an hypothesis in there and probably Network Analysis should prove or reject my theory. I have a list of products and a group of people who give the product to ...
2
votes
0answers
43 views

Cluster analysis on related factors

I am analyzing a public data set of information security incident data and trying to find "clusters" of related factors. Specifically, each incident is analyzed using VERIS for the actor's variety ...
0
votes
1answer
72 views

Topic and subject classification

I have a set of documents that are OCR-ed and represented as a text file. I want to find out what are the documents that are talking about the same subject and maybe about the same person. I started ...