How do we measure the complexity of directed acyclic graphs?

03 November 2023 1 5K Report

Directed acyclic graphs are becoming very useful for creating consensus algorithms in distributed systems. It is important to have a metric to measure the complexity of the directed acyclic graphs. Hence this query.

Kuparala Venkata Vidyasagar

Measuring the complexity of directed acyclic graphs (DAGs) involves various metrics that encapsulate their structural characteristics. Several measures are used to quantify the complexity of DAGs:

Node and Edge Count: The simplest measures involve counting the number of nodes and edges in the DAG. A higher count generally implies increased complexity.

Depth and Width: Depth measures the length of the longest path from the root node to any leaf node, while width indicates the maximum number of nodes at any level. Deeper or wider DAGs tend to be more complex.

Cyclomatic Complexity: This metric counts the number of independent paths through the DAG. A higher cyclomatic complexity implies a more intricate DAG structure.

Entropy: Entropy measures the uncertainty or randomness within the DAG's structure. Higher entropy indicates higher complexity due to less predictable relationships between nodes.

Degree Distribution: Analyzing the distribution of node degrees provides insights into how connections are distributed among nodes. Irregular or diverse distributions often indicate higher complexity.

Graph Density: This metric measures the ratio of the actual number of edges to the total number of possible edges. Lower density can indicate higher complexity, as it suggests sparser connectivity.

Hierarchy Metrics: Measures such as the number of levels, average level depths, or metrics related to tree structures within the DAG can provide insights into its complexity.

These metrics offer different perspectives on the complexity of DAGs, and often a combination of these measures is used to better characterize and understand the intricacies of a particular directed acyclic graph.

Badges
Science topic

Similar topics
Mathematics

More Gokul B Alex's questions See All

How should I go about evaluating cytoplasmic and nuclear Arginase-1 activity?

Hello! I've stained some bright field Arginase-1 Hematoxylin slides, but I'm having a hard time finding any computed histology predicates for evaluating the intensity of the cytoplasm verses the...

03 February 2021 3,039 1 View

Does anyone know why I would have unexplained emission overlap for flow cytometry?

Hello, I am new to flow cytometry, and was just using a sample cell population to train with the technician. The cells were PAC-1 cells split into four groups. Unstained, transiently transfected...

28 January 2021 969 2 View

Does anyone know of a library for R that includes phi?

I'm looking to produce some phi correlations and I'd rather not do it manually, but I can't find a library for R that includes phi.

18 January 2021 2,808 9 View

In SEM, how to interpret standardised regression weights and their significance?

I have a SEM model that I'm having difficulty interpreting. It has one direct effect with a Beta/standardised regression weight that appears to be high (0.80) and significant (p

31 December 2020 7,604 6 View

Does anyone know how to add custom text to a violin plot in r, ggpubr made using the ggviolin line?

I've produced a violin plot for a point-biserial correlation. Main title is there, x and y are labelled, but I want to add a custom text box with the correlation coefficient and significance...

26 December 2020 4,480 4 View

How do I interpret these correlations and p-values?

I've just run a series of point biserial correlation tests in R between whether or not characters were assigned national identities, and attributions given to their behaviours - results shown in...

17 December 2020 9,825 4 View

Is it possible to fuse Deep Learning Net and Clustering Algotrithm?

What I did (unpublished yet) is extract several (e.g. 16) mask features within Mask R-CNN from multiple images, construct a distance metric to compare them to predict the image class. Each set of...

13 December 2020 9,504 2 View

Are there models trained+evaluated on multiple datasets?

Generalization of COVID-19 models is a very serious challenge. I'm trying to find a model (ct scans or x-rays) that was trained and evaluated on multiple datasets. It would be particular...

03 December 2020 8,863 4 View

Are there models trained on both x-ray and ct scans for COVID-19 prediction?

I've only come across models that were trained and evaluated on one of these data. I don't see why it would be a problem to do both, as there are many similar features.

03 December 2020 8,310 3 View

Could anyone suggest me what is the best way/method to isolate total RNA from the platelets?

I have tried to isolate platelet total RNA from the human and sheep blood using TRIzol reagent. After isolation of platelets from the blood samples, total RNA extracted, and quantified using...

02 December 2020 6,165 4 View

What is your perception on using visual analysis or quantitative approaches to evaluate data from single-case research designs (n of 1 trials)?

Results of single-case research designs (i.e., n-of-1 trials) are often evaluated by visually inspecting the time-series graph and computing quantitative indices. A question our research team is...

03 March 2021 687 1 View

How can I make stacked bar graph with scatter plot?

I want to make a stacked bar graph with showing each data value as dots. I tried with graph pad prism, version 6, but could not succeed. Does anyone have tried before making such graphs?

01 March 2021 9,383 1 View

How to evaluate unsupervised clustering metrics when some elements do not have a cluster label in the result?

I run algorithms like HDBSCAN and MeanShift, and compare them with K-means and GaussianMixture. The first two algorithms do not return cluster labels for some elements in the dataset. My question...

27 February 2021 428 3 View

What could be reason for getting such type of graph for complex impedance in case of polymer blend films?

Its effect appears in real part of ac conductivity also. Can anyone suggest any reason behind it?

26 February 2021 3,487 3 View

Can I use a graph from a another source in a thesis?

I have a permission from X company to use their graph from a report, but they have a reference in the bottom left corner of the graph as follows: "Source: Database Y". Is it OK to use this graph...

24 February 2021 2,269 3 View

I have need of XRD graph analysis software for phase identification. Can you please provide links for software tools which can be downloaded?

i am trying to download x'pert high score software, but can't download it. please do suggest software for phase analysis

24 February 2021 5,687 4 View

Could you please suggest to me research in which a relation between the shear wave velocity and the degree of saturation for stone was discussed?

Hi all, I am looking for a graph or a relation that relates the degree of saturation and the shear wave velocity for the marlstone. Looking forward to your suggestions Best Regards

24 February 2021 9,690 1 View

Algorithms to filter corrective max and min from a set of data?

I've got this 5 year Direct Normal Irradiance data I downloaded from https://re.jrc.ec.europa.eu/. I ordered this by year and by every 24 hours because I need the DNI curve by max in summer, min...

17 February 2021 2,777 5 View

There is any numerical criterion for identifying neighbours for Voronoi /Gabriel graphs?

If there is a set of n points in a plan (with known x, y coordinates), can I use a numerical criterion to establish if two points are neighbours, given the definition of a neighbour for Voronoi...

17 February 2021 6,914 4 View

Can anyone name this graph type?

I've attached a recreation of this graph type that I need to make for study reports. The clients have sent them to us in the past, but I am trying to make the reporting process more streamlined,...

15 February 2021 9,795 3 View