# Tagged Questions

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

6 views

### Clustering large graphs - random submatrix SVD. Is it still state of the art?

I am interested in the problem of clustering graphs/datasets with 10s of millions or more feature vectors. I was therefore very interested in this very highly cited paper from 2004 "Clustering ...
13 views

### What are some alternatives to the random surfer model in the Page Rank algorithm?

In the original PageRank algorithm, the authors introduced the idea of a random surfer,who was a user who while surfing the web, could either go from the current web page to a web page by clicking on ...
16 views

### What are some of the existing methods (preferably with implementations) that cluster dynamic brain network data with signed edge weights?

I have a dynamic graph data with nodes and edges attributed to each timestep. The problem is to find how many communities are found at each timestep and what is their membership. I have an existing ...
23 views

### Formalism/name of a graph theory problem

I'm wondering if there's a formalism/well-known name for this graph theory problem: Given $n$ nodes on a map, find the path(s) for visiting the greatest number of nodes given a total constraint on ...
25 views

### Number of neighbors as a function of dimension

I apologize in advance for perhaps an imprecise formulation of the question. If I have a point in 1D, it has precisely 2 nearest neighbors independent of choices. In 2D, if I allow arbitrary ...
93 views

### Is there a supervised learning method for classifying graph walks?

I have geolocational data(coordinates and times with device id), I can bucket this down using say 5m by 5m squares to represent a vertice on a graph. Then following the device id and creating edges ...
31 views

### Similarity measure for clusterings in graphs evolving over time (temporal network)

From what I understand about clusters, they can be obtained from an existing graph at 1 instance of time. But consider the situation of a temporal network, such as a social network, where the graph ...
39 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 ...
14 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 ...
12 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 ...
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 ...
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 ...
13 views

### Directed graph algorithm

Say I have the following graph: ...
24 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 ...
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 ...
22 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 ...
11 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 ...
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 ...
10 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
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 ...
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}) \...
27 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 ...
140 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 ...
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 ...
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 ...
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)?...
45 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 ...
13 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 ...
26 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 ...
34 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 ...
42 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 ...
13 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 ...
21 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) ...
62 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. ...
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 ...
13 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 ...
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 ...
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 ...
57 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 ...
38 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 ...
130 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 ...
57 views

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 ...
340 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 ...
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 ...
25 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 ...
37 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 ...
49 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 ...
24 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 ...