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
1answer
32 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
24 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
20 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
25 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
44 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
84 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
13 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
45 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
29 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
22 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
37 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
28 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
63 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
149 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
50 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 ...
0
votes
0answers
19 views

R - Network Connectivity over the time

I have to analyze if a network (represented as a graph) mantains its connectivity over the time. The data that I've obtained from the simulation is given here, where L1 points out the vertex of the ...
1
vote
0answers
26 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
52 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
38 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
62 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
47 views
2
votes
1answer
129 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
197 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
98 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
67 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
30 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
116 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
20 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
225 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
50 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 ...
3
votes
1answer
85 views

Community finding algorithms in large heterogeneous networks

Consider a network that consists of vertices with various meanings. For example: stack overflow users, keywords and user location when asking/answering a question. In this network, when a user asks a ...
0
votes
1answer
140 views

Why do Bayesian Networks use acyclicity assumption?

Actually, this question is more or less a duplicate of the one which I have asked on math.stackexchange two days ago. I did not get any answer there but I think now here is a better place to ask ...
0
votes
2answers
78 views

Comparing statistics of networks of different sizes

Hi This maybe a basic Stats question. Let say I have 3 networks of different sizes. Size in terms of number of nodes and links. Network n1, n2 and n3 have v1, v2 and v3 nodes and l1, l2 and l3 ...
2
votes
1answer
66 views

Detecting strong currents in a sparse directed graph

I have a very large, sparse, weighted, directed graph. The structure is such that it mainly consists of strings of nodes connected with highly weighted edges. These strings can be connected by weak ...
7
votes
1answer
138 views

Force-directed methods to draw graphs

i am working to create a mapping of the adjacencies between 100 consumer goods. I have created an adjacency matrix based on product characteristics, and then create an i-graph of the graph/network ...
1
vote
0answers
46 views

Generate synthetic data from a graph (e.g., bipartite)

Does anyone know of literature describing methods for generating synthetic data from a graphical structure that has been learned from observations of real data? The graph, depending on the type of ...
-1
votes
0answers
43 views

From relational database to graph: file formatting and software [closed]

I am approaching graph theory (I have a background in social sciences) to map a discussion forum. My forum/network has four types of vertices: author of thread, thread, comment and author of comments ...
1
vote
3answers
233 views

Correlation Clustering

Correlation Clustering : Given a signed graph where the edge label indicates whether two nodes are similar (+) or different (−), the task is to cluster the vertices so that similar objects are ...
1
vote
1answer
106 views

Software for working with exponential random graphs

I am looking for software packages for working with exponential random graph models (fitting/generating them and sampling from the graph distributions). I have only found two packages so far, both ...
1
vote
0answers
25 views

Grouping observations based on variables that sum to one

I have a problem where I am trying to group observations (most likely using k-means or a similar unsupervised learning tool) where each observation includes n-variables, with the total sum of these ...
0
votes
2answers
200 views

What are the statistical features of a network/graph without community structure?

I want to filter out networks/graphs which are just a single community rather than interconnected communities. Each community can either be a random graph or a star graph, but there should no ...
0
votes
1answer
66 views

Random geometric graph connectivity

Given N random points uniformly distributed in the unit square, and a distance d, i can generate a matrix in the following format: ...
1
vote
0answers
46 views

Statistical inference about degree of a node in a genetic network

I am working on Gene-Gene interaction networks. I build a graph by adding edges between genes (nodes) representing statistical interaction in prediction of a quantitative parameter value (say, brain ...
2
votes
0answers
54 views

how does one predict edges / links / connections on a weighted directed graph network?

Given an adjacency matrix A for a weighted, directed graph (so matrix elements are not just 0/1 and the matrix is not symmetric), are there any good methods for predicting new edges? I have a VERY ...
1
vote
0answers
53 views

Assessing the consistency of an estimator of the average path length of a large network

I have found the following in a network-science article and would like clarification of what the authors are claiming: We observe that the root mean square of the difference between the empirical ...
4
votes
0answers
107 views

Distribution/expected length of the shortest path in infinite random geometric graphs

Consider an infinite random geometric graph $G(\rho,d)$ in which vertices are uniformly and independently scattered over the 2D plane with density $\rho$ and edges connect the vertices that are closer ...
8
votes
1answer
156 views

Density of robots doing random walk in an infinite random geometric graph

Consider an infinite random geometric graph in which the node locations follow a Poisson point process with density $\rho$ and edges are placed between the nodes that are closer than $d$. Therefore, ...
2
votes
0answers
101 views

Appropriate threshold to map a similarity value to an edge in a graph

In order to cluster users given a user-item binary matrix data, I am planning to first find user's similarity (Jaccard) and then use graph theory to isolate clusters (communities). I need to map the ...
3
votes
2answers
346 views

Network Visualisation for huge dataset composed of many unconnected clusters

I have a dataset which consists of 190,455 nodes and 1,241,638 edges. These can be broken down into a set of 2300 subgraphs which are not connected to each other. I am having trouble creating ...
3
votes
1answer
96 views

Spectral clustering of graph

I am trying to cluster the graph using spectral clustering. However I am unaware of the number of classes that exist in the data. Will it be a good idea to do PCA on the adjacency matrix to find ...