Graphs are abstract representations of objects and their mutual relations, where the objects are 'nodes' and the connections among them are 'edges'.

learn more… | top users | synonyms

1
vote
1answer
17 views

What is the definition of a kernel on vertices or edges?

I am currently trying to perform clustering on a collection C of undirected and unlabeled graphs. I decided to use to a kernel on graphs to obtain the kernel matrix of C. Then I can derive the ...
0
votes
0answers
13 views

What does y * dy mean in this context of a time series graph?

I'm trying to smoothen a time series plot to derive cycle times of a machine. Y-axis is total power output, x-axis is time(s). My first data manipulation is that I find dy between each measurement ...
1
vote
0answers
10 views

Random Walk: Right p-value method?

Based on a stochastic matrix/graph $G$, I want to conduct a series of random walks to get an idea which are frequent interaction partners for a starting node (not only connected by the first edge). I ...
0
votes
0answers
24 views

Using spectral or hierarchical clustering for small world graph

Suppose we have a weighted edge graph with small-world property and we want to cluster the nodes of the graph based on the edge weights as similarity of nodes (the weight of an edge shows the ...
0
votes
0answers
5 views

Weighted mean / average where you reward the lowest value / cost / distance

Best I've several weather-station (200), placed across the country (508 municipalities). Now, I would like to prescribe the weather info, e.g. temperature, to each of the municipalities of that ...
0
votes
0answers
17 views

Family relationships and random assignments [migrated]

Suppose I deliver a special note to 2% of a population at random. What is the probability that such note has been delivered : parent and child cousin and cousin Assume a birth rate with a mean of ...
0
votes
0answers
11 views

Directed graph algorithm

Say I have the following graph: ...
1
vote
1answer
23 views

Prediction of vertex scores in a bipartite graphs

I have a bipartite graph with two sets, A and M, of nodes. Every vertex in M has a score associated with it. I have two tasks: To every vertex a in A, I have to assign a score based on the scores of ...
0
votes
0answers
14 views

Graph analytics: choosing best location

Lets say I have the latitude and longitude coordinates of various people. I also have the latitude and longitude of 2 specific locations. I got a function that calculates the distances between the ...
1
vote
0answers
17 views

Effect of partitioning on graph density and edge cuts

When a graph is partitioned using partitioners like METIS, what are the expected effect on density (ratio of number of actual edges to the maximum total number of edges ) and edge cuts(comparison ...
0
votes
0answers
10 views

What is the best way to predict communications in a large social network?

I need to make a recommendation system that would predict friends for users in the social graph. The number of users is around 1.500.000. I thought of creating all possible pairs of users and then ...
1
vote
0answers
21 views

Multiple testing correction in a graph

I am doing some statistical tests over a graph. Namely, each subject in my study has a graph (composed of nodes and edges), where each edge has two different values (let's call them F and S). I am ...
0
votes
0answers
8 views

Difference between adversarial, random and stochastic ordering in data streams

Kindly explain the difference between adversarial, random and stochastic ordering in data streams in layman terms
0
votes
1answer
28 views

maximal subset - include nonuniform node weights and node values

I am trying to solve a graph theory problem. I have an undirected graph where the nodes have node weights n and edges have edge weights g. I want to be able to select the subgraph such that the ...
3
votes
1answer
43 views

Probability of at least one triangle in Erdos-Renyi graph

This is a well-known problem in random graph theory, where we show that if $X$ is the number of triangles in $G(V,E,p)$ with $p=o(\frac{1}{n})$, we can show that $$ P(X \geq 1) \geq 1-o(\frac{1}{n}) \...
0
votes
1answer
24 views

igraph shortest path export as vector [closed]

This is probably a very simple question but I cannot seem to solve it: I'm using the igraph package and want to export the vpath part of the get.shortest.paths output as a vector so that I may work ...
1
vote
1answer
111 views

Correct way of computing Shannon Entropy of a walk

Take for example a walk such as: ["school", "work", "home", "kindergarten", "home", "school", ...] # or simply [1, 2, 3, 4, 3, 1, ...] What's the correct way of ...
0
votes
0answers
15 views

How to make educated guess about movement of people through graph?

I have data about weekly counts of people on entry points (orange circles on the picture below) and need to make educated guess about their counts at destination points (marked by green stars). I know ...
3
votes
0answers
20 views

Is there an estimate for the variance of average minimum path length for Erdős–Rényi graphs?

I am calculating the average minimum path length of Erdős–Rényi graphs. I am using the $G(N,n)$ model whereby a $N$ node graph with $n$ edges are generated uniformly. I found the expected average ...
0
votes
0answers
8 views

Maximum vocabulary distance

Given a vocabulary with size m (the number of letters in it) and words of length n, what is the maximum word distance (number of differing letters) for a text with length o (the number of words in it)?...
1
vote
1answer
43 views

Vulnerability index for every node of graph

Given a particular undirected graph with n nodes, is there an index that would characterize the vulnerability of each of the nodes? By vulnerability I mean the susceptibility of the graph to ...
0
votes
0answers
12 views

Ways to summarize the number of users and messages sent as a comparative quantity?

I have a dataset where there are different groups of users, and the number of users in each group are different. They each send out messages to members in their own group and other groups. Eg. 3 users ...
1
vote
0answers
22 views

Information entropy in a direct graph?

I have a directed graph, and each edge in the graph has a probability, representing certainty in the edge. How can I represent overall uncertainty in the network. I was thinking of using an ...
0
votes
0answers
30 views

Got an entropy-ish function for a multinomial distribution? Graph theory and Bayes net related

I have a discrete variable $X$ that can take on one of three states; $a$, $b$, and $c$. Thus it has two parameters $p_a = P(X = a)$ and $p_b = P(X = b)$, of course $P(X = c) = 1 - p_a - p_b$. I am ...
3
votes
0answers
34 views

Combining bipartite graph with one mode graph

I have a director-firm bipartite graph. In addition, I have a kinship relationship graph which includes the directors. I would like to combine the two adjacency matrices, but that violates the basic ...
0
votes
0answers
12 views

Looking for algorithm that is a discounted min-cost-maximum-flow calculation

In terms of graph theory I am very familiar with minimum-cost maximum flow, connectivity and ...
0
votes
0answers
20 views

Is Pearson correlation on graphs a valid approach to compare undirected weighted graphs?

I have came to several instances where researchers use Pearson correlation to compare edges of two graphs to find out if they are similar. For example, given two symmetric adjacency (proximity) ...
2
votes
1answer
59 views

are there any alternatives to graph theory?

I was planning to use a graph theory / page-rank approach to find the most influential person in an organization. Influential person is someone who drives a lot of activity in the organization. ...
0
votes
0answers
28 views

Conditional independence representation in graphs

My question is related to the second part of this question here below in this url regarding conditional independence and its graphical representation Assuming we consider an example ...
1
vote
0answers
12 views

Cluster into communities a graph with negative edge weights representing repulsion [duplicate]

Consider an undirected graph $g$ with some edges having negative weight - all weights in $[-1,1]$. We are seeking communities or clusters. Negative edge weight means repulsion and positive means ...
2
votes
1answer
40 views

Probabilities in markov graphs

I have a first order markov graph which looks like Now I was told if we make B an absorbing state(NULL) the graph simplifies to I was also told that the conversion probability is 1 in the first ...
5
votes
0answers
157 views

Multiple eigenvectors in graph spectral clustering

In Newman's PNAS 2006 paper Modularity and community structure in networks, the first eigenvector splits the graph in two clusters, and then each cluster can be further divided by eigenvector of a ...
3
votes
0answers
54 views

Theoretical link between the graph diffusion/heat kernel and spectral clustering

The graph diffusion kernel of a Graph is the exponential of its Laplacian $\exp(-\beta L)$ (or a similar expression depending on how you define the kernel). If you have labels on some vertices, you ...
1
vote
0answers
36 views

Comparing two graphs/markov chains by comparing their clusters

I have an undirected graph representation of my system (a dynamical system), i.e. I have some labelled nodes and bi-directional edge weights, so everything is in a Markov matrix form. Now I can form ...
3
votes
2answers
126 views

Statistical Test for “clumpiness” of graph

My data set is a list of items and for each item a list of all other items that this item has cooccurred with. Effectively this is an adjacency matrix for a non-directed graph. I'm looking for some ...
1
vote
0answers
57 views

Bayesian link prediction problem: advice to deal with unfamiliar likelihood

Imagine that we have a graph $G$ such as the one in the figure and that we take a snapshot of this network every day. Our hypothesis is that the probability that node $i$ will have at least one new ...
5
votes
3answers
300 views

Graph clustering algorithms which consider negative weights

I have a graph instance with weighted directed edges which values can be in range [-1,1]. I need to do clustering on this graph, in order to find out groups in which vertices are more correlated. I ...
1
vote
0answers
41 views

Modeling a Classification Problem with an Undirected Graphical Model

I have an undirected graphical model problem which I'm looking for some help on. So, the goal is to perform multivariate classification: based on a set of observations, I want to predict the correct ...
1
vote
0answers
24 views

dynamic rooted tree graph

Suppose I have a tree graph rooted at point P1, if I moved this point (P1) to another place in the tree, can I change the data structure by changing the points IDs so that the graph still rooted at P1 ...
1
vote
1answer
35 views

How can I solve this graphical model?

I have a classification problem, with the following structure. There is a fully-connected graph, and each node needs be assigned a class label. Every pair of nodes in the graph has a probability ...
0
votes
1answer
38 views

Validating Personalized Pagerank Matrix computation in R

My question is with reference to this paper here This is an excerpt from the paper From the similarity of the two equations we can see that if ppr_alpha_u is added up it will be equal to pr_alpha ...
0
votes
0answers
23 views

Computing and validating personalised PageRank in R

I have been trying to calculate personalized pagerank matrix in R however I am facing some logical issues. As described by the paper by Archak et al found here, in section 5.2 the sum of the column i ...
0
votes
0answers
37 views

Small Point Set Matching

I'm trying to match two small sets of points (~10 each) and can't find a particularly successful algorithm. All points have a known co-variance matrix and are only 2D. Many points in each set are ...
1
vote
1answer
534 views

Calculating Personalized PageRank in R

Is there anyway I can calculate the personalized PageRank in R? A little bit about Personalized PageRank The Personalized PageRank matrix is defi ned as a n by n matrix solution of the following ...
3
votes
1answer
249 views

How to test statistically whether my network (graph) is a “small-world” network or not?

A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps. ...
0
votes
0answers
18 views

Comparing two graphs and calculate probability they come from the same source

I'm looking at data related to people badging in and out of a plant. I know where and when a person uses their badge to gain access. What I'd like to do is take a certain amount of data for an ...
1
vote
0answers
87 views

Model for supervised learning on graphs with varying structure

Colorization problem is considered. I have a training set of unordered graphs (images) with varying number of vertices and edges (color regions and adjacency between them, resp.). A fixed number ...
3
votes
0answers
135 views

Highly Connected Subgraphs cluster

i'm studying a method to cluster similar topic represented in a graph like this: The result must be: [0] = 1,2,4 [1] = 3 I tried Markov Cluster Algorithm but ...
0
votes
1answer
130 views

Should I use IN or OUT degree in Network Diffusion Model of Twitter network using iGraph?

I'm trying to run Independent Cascade Model for my Twitter graph to see who I have to stimulate to get the maximum cascade. This code is inspired by http://php.scripts.psu.edu/hxc249/code_segments/...
6
votes
1answer
88 views

What methods exist for tuning graph kernel SVM hyperparameters?

I have some data that exist on a graph $G=(V,E)$. The vertices belong to one of two classes $y_i\in\{-1,1\}$, and I'm interested in training an SVM to distinguish between the two classes. One ...