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
9 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
39 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
17 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
24 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)?
-1
votes
0answers
19 views

Given some nodes in a Bayes net, what is the probability of another node being true?

By example: Say LC = False, MP = True. What is the probability of CG being true then?
2
votes
3answers
78 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
25 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
27 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
13 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
15 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
11 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
10 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
8 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
24 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
18 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
15 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
30 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
40 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
41 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
46 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
30 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
46 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
86 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
21 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
37 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
84 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: ...
1
vote
1answer
138 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
15 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
51 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 ...
0
votes
1answer
31 views

Possible problem for Network Analysis

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 ...
0
votes
0answers
37 views

Recommendation System with Graph Database

Hi I'm looking into creating a recommendation system based on a graph database for an ecommerce website. Basically something like amazon, "if my customer's have bought these products recommend some ...
2
votes
0answers
40 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
62 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 ...
3
votes
0answers
69 views

Facebook users similarities

I'm searching for a similarity metric such that given two Facebook users it returns a value that reflects how similar the two users are. The similarity metrics must take into account (at the same ...
2
votes
2answers
207 views

Are there any probabilistic models for graph-based recommender systems?

All I can find now is somehow based on random walks or graph kernels, which is nice, but I want to have a more or less solid probabilistic foundation for my recommender system for bounds and ...
1
vote
1answer
60 views

Inference in undirected graphical models.

I know Bayesian or Directed Graphical models are good for fast inference using message passing techniques. But how does it work with undirected models? With directed models, you moralize the graph ...
1
vote
0answers
27 views

The best estimate of age of a person in social network

Suppose that we have any social network (i.e. we know who is a friend of whom) and for some nodes in the network (i.e. the users), we also know their age (but not for everyone, as in a real network). ...
1
vote
0answers
59 views

smoothing nodes values on a graph given adjacency matrix

I am currently looking for a method to smooth values on a graph (composed of vertices and edges). For example I have a graph with a set of nodes V and I want to be able to smooth it. I could have ...
1
vote
1answer
48 views

Expected assortativity coefficient of random graphs

I am wondering whether there exist a closed-form expression for the expected assortativity coefficient (http://arxiv.org/pdf/cond-mat/0205405.pdf) of an Erdos Ranyi random graph model $G(n,m)$, where ...
3
votes
0answers
69 views

Regression analysis to estimate affinity or antipathy among celebrity wedding parties

Please consider the following plot of a graph: Each node represents a wedding party while each edge is the relation between the two parties expressed in terms of the number of people who attended ...
0
votes
0answers
60 views
3
votes
1answer
177 views

Difference of Prediction between Graph Representation and Data Matrix Representation

In data mining, data can be usually represented in different forms such as records of a matrix, graphs or ordered data. While we find in research different papers addressing methods or solutions for ...
10
votes
2answers
217 views

What does it mean when all edges in a real-world network/graph are statistically just as likely to happen by chance?

I've been using the backbone network extraction method outlined in this paper: http://www.pnas.org/content/106/16/6483.abstract Basically, the authors propose a method based in statistics that ...
1
vote
1answer
179 views

How to quickly build an interactive diagram modeling relationships between nodes from file input?

I hope this finds someone with the right expertise here. I am currently working with a data set on product information that has - a defined search tree structure - product types - synonyms for ...
0
votes
1answer
80 views

Graph Theory - Creating an Index of Familiarity, Given Trade Frequency Counts

Set Up I'm hoping to create an "index of familiarity" between traders on a barter market. I have data from a peer-to-peer barter market (i.e. people come in with their wares, and can trade with ...
4
votes
0answers
34 views

What is the distribution of edge lengths for a Euclidean minimal spanning tree?

Suppose that you have a Poisson point process in $\mathbb{R}^d$ with rate (density) parameter $\rho$; I particularly care about $d=2$ if there is a solution in this special case. Given a finite ...
4
votes
1answer
124 views

A statistical model for a sample of independent networks

Based on the lack of responses to my previous network question, perhaps this is not quite the place to ask this question, but I'll give it a try. I am planning a series of studies that involve small ...
0
votes
0answers
34 views

How can I model random graphs (trees) with deterministic constraints?

I have been trying to represent a tree structure as a random graph, but so far my research has led to variations of random graph models and I can't see studies which may help me leverage some of the ...
3
votes
1answer
313 views

Centralization measures in weighted graphs

I'm using the igraph package in R to analyze network data. I'm currently trying to calculate some centrality measures for the ...
1
vote
1answer
78 views

What is the standard format of the equation that represents the production of this daughter isotope?

I have an idea about producing a genetic algorithm. But it involves using a relationship which believe could be defined as a horizontal Asymptote. I have found an image that depicts the type of ...