Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

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

0
votes
0answers
14 views

Which regression used for normalized count data

I am working with social network data. I have multiple networks of various sizes and I'm calculating indegree (the number of connections between people) in each of the networks. I've been told to ...
0
votes
0answers
11 views

How to approach node/graph classification in an event?

I'm facing a new project and thought about maybe going in the direction of Graph-Neural-Networks. My data comes in the form of events (unrelated to each other), the data in each events contains a 2D/...
2
votes
0answers
13 views

Adjacency matrix of amino-acid residue [closed]

How to get the mathematical representation of the chemical bonds in protein residue or the whole protein? Is it possible to get the connectivity matrix or a pairwise description? The example in the ...
0
votes
1answer
15 views

Dividing datasets into fully-correlating subsets

I have a dataset of $N$ variables of which I know that (at least) one combination of their disjoint subsets results in non-negative correlation coefficients for all variables in these subsets. The ...
0
votes
0answers
21 views

Why does a minimum value cutoff in edge values create this shape in the log-log plot of the edge values aggregated to start nodes?

I have a weighted network dataset that looks like this: The prev and curr values contain webpages, and n is the number of times users went from the prev webpage to curr webpage. So, each data row is ...
0
votes
0answers
10 views

If I(G) = I(G') do they have the same skeleton and the same v-strucures except those in complete (sub-) graph?

I thought if two different graphs G, G' have the same skeleton and the same v-structure, then I(G)=I(G′) and I(G)≠∅. But does the converse also holds? In this case a complete graph doesn't apply ...
0
votes
0answers
13 views

Combining centrality into one based on same data type

I'm working on a project that involves count data (specifically number of interactions) from multiple different districts in a specific area. Our team has been talking about calculating a few ...
0
votes
1answer
17 views

Determining the closeness of nodes by their neighbours

Background I have a directional network that is comprised of two types of nodes, business_sector nodes, and event_type nodes. ...
2
votes
1answer
34 views

Range of eigencentrality scores

I could not find the answer to this question online. In a graph, what is the range of possible values of eigenvector centrality scores? EDIT: Here is an example: ...
1
vote
0answers
29 views

how to make sure the dependent and independent variables measure the same thing?

I am trying to build a model that measures the importance of musicians social network on their number of gigs. I use graph theory and construct the social network based on the line-up of events for ...
0
votes
0answers
13 views

How to interpret networks with multiple states (e.g. timeseries, conditions, etc.) that have same node set?

Apologies if this is too general but I have been thinking about it all weekend and wasn't sure how to move forward with the idea. Here are the types of networks I am dealing with below: I have 2 ...
0
votes
1answer
59 views

Densest subgraph : density of an intersection

I found an exercice in my textbook and I can't find the answer : $G = (V;E)$ an undirected graph. $H_1 = (V_1;E_1)$ and $H_2 = (V_2;E_2)$ are two densest subgraphs in G, i.e., for any subgraph $H = (...
1
vote
0answers
46 views

Bayesian Networks - Factor Graphs - Belief Propagation - Numerical stability

I am trying to do inference for a Bayesian Network with discrete probabilities. I converted the network to a factor graph and implemented the sum-product algorithm (belief propagation). My goal is ...
0
votes
0answers
24 views

How can I generate random DAG's in a good way?

I am trying to generate random DAG's (Directed Acyclic Graphs)... However, the result is not very satisfying to me; What I am doing: I generate a random graph with the Erdős–Rényi model; More ...
1
vote
0answers
18 views

Conceptual question: A confidence interval around the mean for t-values

I have a weighted graph of an airport network, where each node is an airport (associated with an N, or the number of flights landing at or leaving the airport). The ...
1
vote
1answer
8 views

Manber's graph-partitioning algorithm implementation

I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File. Generally speaking ...
0
votes
0answers
22 views

Finding most valuable paths

I am trying to analyze a data set of user journeys. My data looks as follows ...
0
votes
0answers
11 views

Computing power for linked (i.e., graphs) vs. non-linked data

Why processing linked data (i.e., graphs) require much higher computing power than processing non-linked data?
1
vote
0answers
23 views

How to calculate associated degree of freedom of linked nodes in graph

I am working on text analytics and building a knowledge graph with high frequency entities (noun chunks) as graph nodes and their linkage between co-occurrence in a sentence as edges. I am able to ...
2
votes
3answers
82 views

How to find strongly connected subgraphs in a graph? [duplicate]

I have a simple, undirected graph where I'd like to detect "natural" subgraphs where vertices are connected intensively internally but sparsely externally. The problem is that I have no exact hint ...
0
votes
0answers
9 views

How to build a conversational graph knowledge?

I could not find a solution for my problem, browser points to chatbots. I have 5 or more people sitting around the table. I want to build a knowledge graph from their conversation. Where can I read ...
1
vote
1answer
86 views

Centrality of a directed network with edge weights - Gephi

I have the following network of court judgments in the form of a big network.(50k+ nodes and 100k+ edges with weight values). The size is the number of citations. The idea is that court judgments work ...
1
vote
0answers
32 views

Similarities / suggestions of multi-attribute entities

Dataset: I have 200 000 entites, these have zero or more of 1000 attributes (commonly 1-20 of them) The attibute relation is weighted 1-3 Its stored in a relational database modeles as Entity, ...
0
votes
1answer
123 views

Assortativity coefficient in igraph

In the context of Social Network Analysis, I want to compute the homogeneity of different networks for specific attributes. For this case the igraph package contains the method assortativity() to ...
1
vote
1answer
93 views

Computation of Network Homophily / Heterogeneity

I am quite confused about the calculation of network homophily in network analysis. Right now I am computing the homophily using the following function, which has been written and also described by ...
0
votes
0answers
22 views

Investigating the change of a network / factorial structure over time

I have several variables (questions from a questionnaire) that regroup into several factors (using factor analysis). However, I would be interested in knowing how this factorial structure changes ...
1
vote
0answers
15 views

How to get accurate shortest paths for signed weighted graphs with negative cycles?

I work with resting state functional data and my lab supervisor prefers to use signed, weighted, partial correlation networks (it's fairly standard in rsfc analyses). An unfortunate characteristic of ...
4
votes
0answers
85 views

How to estimate passengers destinations from flightradar data?

We have a graph with vertices corresponding to airports and edges corresponding to flights between those airports. On edge between airports A and B we have and number of passengers transferred from A ...
2
votes
0answers
29 views

How to measure “cyclicity” of a directed weighted graph?

Say you have a weighted directed graph with (potentially) some cycles in it. You want to have some sort of a measure of how "cyclical" this graph is. The requirements are: This measure C=0 on an ...
0
votes
0answers
69 views

agglomerative clustering of undirected weighted graph

Let's say I have a simple graph of undirected, weighted edges. I want to agglomerate nodes one-at-a-time by combining the two nodes which have the highest weighted edge, recalculating remaining edge ...
0
votes
1answer
22 views

How to Cluster Hierarchical Network Data

I have thousands of "small" networks that are strictly hierarchical in nature. Here is an example (some are much deeper, much wider etc) but this is the strict structure: How can one cluster (e.g. k-...
4
votes
2answers
71 views

How to uniformly sample vertices from a large graph with given distance from a fixed vertex?

Given an undirected graph $G=(V,E)$ and some vertex $v_0\in V$, let $V_k=\{\,v\mid v\in V,d(v_0,v)=k\,\}$ be the set of all vertices with distance $k$ to $v_0$. How can I quickly draw uniform samples ...
0
votes
0answers
70 views

Graph-Based Semi-Supervised Learning for NLP Text Classification

I have hundreds of various job titles, where some of the titles may sound different but ultimately should be classified to be the same position (ex. Call Center, Call Center, Customer Contact Center ...
1
vote
0answers
67 views

What is the most efficient implementation of the min-k-cut algorithm?

Simple question, I'd like to apply min-k-cut algorithm on a graph to partition the graph in k clusters by minimizing the sum of edges cut during the formation of clusters. In my case I already know k ...
1
vote
1answer
30 views

Clustering: Clique vs. Agglomerative with Complete-Link

In my data, I have a defined a symmetrical relation $R$ where $R(i,j)=R(j,i)$ indicates that $i$ and $j$ are closed each other. I need to find cliques $C_1,C_2,\dots,C_n$ where $C_k\cap C_l=\...
0
votes
1answer
41 views

Graph-convolutional neural networks---how to determine feature matrix

I've been recently studying the GCNs---graph-convolutional neural networks. Given a triplet (A,F,C), where A is the network-adjacency matrix, F the network feature matrix and C the matrix of classes, ...
1
vote
0answers
51 views

Quantifying information loss between a graph and a hypergraph

In some of the literature relating to hypergraph applications, there is an argument about information loss when representing data as a graph compared to a hypergraph. For example, the well known ...
0
votes
0answers
23 views

What are the available metrics of community structure quality in a graph?

I know that modularity can be used for evaluating the "quality" of a community structure found by an algorithm in a graph. What other options are available? I need to evaluate different algorithms ...
1
vote
0answers
31 views

How to represent a graph in a vectorized format suitable for ML?

Suppose we want to represent graphs (knowledge graphs, or other types of graphs/networks) in a vectorized format, such that it is suitable for a neural network or other machine learning technique. ...
0
votes
0answers
148 views

What is the interpretation of K-means clustering on a weighted adjacency matrix?

Suppose I have a weighted adjacency matrix A representing a graph G. I use K-means on this matrix to group vertices together. What is K-means finding exactly? I mean, what is the interpretation of ...
0
votes
0answers
42 views

Partitioning a graph based on sum of edges weights inside the groups and leading outside the groups?

Suppose I'd like to partition a graph in communities. My objective would be to find the best set of k groups where by "best" I mean the set of groups that maximizes, for each group, the sum of weights ...
0
votes
0answers
17 views

Partition a graph around two vertices

Given an undirected weighted graph G and two distinct vertices (v1, v2) in the graph, I want to create two partitions V1 and V2, such that v1 is a member of V1, v2 is a member of V2, and sums of ...
0
votes
0answers
50 views

Community Detection in Multilayered Network

I want to implement Community Detection on a complicated Multilayered network with not only inter-layer weights and intra-layer weights but also edges between two nodes of different layers (example: ...
1
vote
1answer
149 views

Directed Acyclic Graph of Stan Model

I have the following Stan model: ...
3
votes
2answers
124 views

How to handle disconnected graphs in spectral clustering?

I am writing a clustering algorithm based on Normalized spectral clustering. When I try and compute the generalized eigenvectors like so: ...
1
vote
1answer
48 views

How to generate networks of a certain density?

How can you generate small world or scale-free networks with a certain density, say .3? In the case of random networks it seems easy because an edge is drawn based ...
0
votes
0answers
74 views

NN Accuracy and Understanding tensorflow-graphs

If I test accuracy using the below code while training, then it works well. If however, I use a separate function then it outputs the wrong value (about 20 times too small). There must be something ...
0
votes
0answers
35 views

Connectivity vs. density for random, small world and scale-free networks

I am trying to understand a paper by reconstructing the the analyses discussed in the Validation study section, however, I am confused when it comes to how a network metric is used. Specifically, the ...
0
votes
0answers
19 views

Does recursive partition of a graph using min-cut yield the minimum cumulative sum of edges weights?

Suppose I have an undirected graph with weigthed edges a and vertices. I want to partition the graph in N subgroups. Suppose that any time a cut occurs, I sum the weights of the edges which belong to ...
0
votes
1answer
25 views

What is the state of the art process for finding isolated communities in graphs?

Is there a state of the art process to follow for finding isolated communities in graphs? I know there are a lot of algorithms available, but I struggle to find a set of steps for preprocessing and ...