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
7 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
30 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
22 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
53 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
106 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
41 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
17 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
23 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
40 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
0answers
26 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
56 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
30 views
2
votes
1answer
105 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 ...
9
votes
2answers
174 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
67 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
58 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
29 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 ...
3
votes
1answer
108 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
15 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 ...
2
votes
1answer
163 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
42 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 ...
2
votes
1answer
71 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
124 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
59 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
56 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
134 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
41 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
204 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
84 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
23 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
190 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
62 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
44 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
48 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
52 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
96 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
151 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
91 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
282 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
83 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 ...
2
votes
1answer
109 views

Adversarial noise in PCA

PCA is known to be quite sensitive to outlier noise (and this is why several Robust PCA techniques exists.) However, I am looking for a concrete example of sensitivity of PCA to adversarial noise that ...
1
vote
0answers
83 views

How to correlate graph properties with vertex attributes?

I have a directed graph, S, where each vertex stores several integers of attributes. I think it might be called a "attribute relational graph" or just an old fashioned "attributed graph". The networkx ...
5
votes
1answer
834 views

BIC or AIC to determine the optimal number of clusters in a scale-free graph?

I am currently trying to partition a scale-free ("big") graph (around 20k vertices, 500k edges) into appropriate sub-graphs. Having derived the Laplacian of the graph, I tried running an approach ...
2
votes
2answers
197 views

Finding communities in online social networks by removing nodes

I want to carry out Graph Clustering in a huge undirected graph with millions of edges and nodes. Graph is almost clustered with different clusters joined together only by some nodes (kind of ...
3
votes
0answers
61 views

How to learn similarity of typed/attributed graphs?

I have a question for graph machine learning gurus :). For this project I'm working on, I need to be able to learn similarity between typed graphs. By typed I mean that every vertex and every edge of ...
4
votes
2answers
162 views

Nonparametric test to compare link prediction algorithms

I have some experimental data, and I want to use a non-parametric test to verify my results. I am considering link-prediction on complex networks. I have a complex network $N$ and an algorithm/model ...
4
votes
1answer
504 views

Randomly generated adjacency matrix in R

I'm wanting to generate random connected directed acyclic graphs, and am wondering if there is a way of populating an adjacency matrix in R which would represent the aforementioned. Something similar ...
-5
votes
1answer
88 views

Probability that a component belongs to a giant component

In a configuration model where each node has a degree 2. What is probability that a node belongs to a component of size n.
0
votes
2answers
110 views

Belief propagation on MRF with complex cliques

Is there a belief propagation algorithm for exact inference on a MRF with complex clique structures (i.e. ones involving more than 2 neighbours)? For MRF's with cliques that only involve pairwise ...