2

Given a matrix that describes the edges' and their weights of a connected graph (see below) I want to extract a subgraph based on a threshold value x for the edges' weights. In literature, I read that one can search for the maximal x, such that the induced subgraph is connected.

Since the initial graph is assumed connected, there must be a critical threshold x-critical that the extracted subgraph is connected for any x <= x-critical.

I was wondering how can this implemented in R. For example, my matrix (weights.matrix) looks like

| FROM | TO | WEIGHT |
| A    | B  | 0.0042 |
| A    | V  | 0.23   |
| G    | W  | 0.82   |
| ...  | ...| ...    |

and I'm creating the whole graph, by using the igraph package like:

g <- igraph::graph_from_data_frame(weights.matrix, directed = TRUE)

Is there any way to check repeatedly - by applying a different threshold value in the weights from min() to max() - if the occurred graph is connected? I searched in google for such feature in igraph but couldn't find anything helpful.

Here is some code for building such a graph.

library(igraph)

mat <- expand.grid(LETTERS[1:10], LETTERS[1:10])
mat$Weight <- runif(nrow(mat), 0.01, max = 1)
mat <- mat[mat$Var1!=mat$Var2, ] 

g <- graph_from_data_frame(mat)

Also here is a paper referring that technique in pdf's page 15 , section 5 the fourth. You can consider the edge relevance as the edge weight discussed here.

double-beep
  • 5,031
  • 17
  • 33
  • 41
J. Doe
  • 619
  • 4
  • 16
  • When asking for help, you should include a simple [reproducible example](https://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example) with sample input and desired output that can be used to test and verify possible solutions. – MrFlick Jul 02 '18 at 20:32
  • I edited my initial post and add some code example. – J. Doe Jul 03 '18 at 07:17

1 Answers1

1

I work in python, not R, so the following is just pseudocode.

I would work on the adjacency matrix (not an igraph object) as this will be fastest. Let A be the adjacency matrix, W a sorted list of weights and w an element of W. The basic idea is to iterate over all weights in the adjacency matrix A, threshold A at each weight and check for empty rows (and columns iff the graph is directed).

Then the pseudocode for the directed case is:

function (A) -> w

W = sort(list(A))

for w in W:
    A' = A > w
    for row in A':
        if sum(row) == 0:
            for col in A':
                if sum(column) == 0: 
                     return w

There are many ways to optimise this, but this gets the basic idea across. #

The fastest way would probably be to compute the maximum weight for each row and each column, maxima_rows and maxima_columns, find the minima of those, min_max_row and min_max_col, and then take the maximum of those two values to get w.

EDIT:

In python, the fast approach would look like this:

from numpy import min, max

def find_threshold_that_disjoints_graph(adjacency_matrix):
    """
    For a weighted, fully connected graph, find the weight threshold that results in multiple components.

    Arguments:
    ----------
    adjacency_matrix: (N, N) ndarray of floats

    Returns:
    --------
    threshold: float

    """
    maxima_rows = max(adajacency_matrix, axis=1) # (N, ) vector
    maxima_cols = max(adajacency_matrix, axis=0) # (N, ) vector

    min_max_rows = min(maxima_rows) # float
    min_max_cols = min(maxima_cols) # float

    threshold = max([min_max_rows, min_max_cols])

    return threshold
Paul Brodersen
  • 11,221
  • 21
  • 38
  • Could such algorithm help to what we are looking for (https://www.geeksforgeeks.org/bridge-in-a-graph/)? – J. Doe Jul 03 '18 at 10:18
  • I thought the graph is weighted and initially fully connected? That page seems to discuss the unweighted case which you would want to approach very differently. – Paul Brodersen Jul 03 '18 at 10:30
  • Yeah your thought was right. I'm talking for weighted graph too. I – J. Doe Jul 03 '18 at 11:07
  • The pseudocode above implements the procedure on page 15 in the paper you linked and your problem description. Whether or not that translates well to the notion of "bridges" depends on what those weights actually physically represent. Without intimate knowledge of the data acquisition and processing that question is unanswerable. – Paul Brodersen Jul 03 '18 at 11:44
  • Hi again. Is the fastest way you suggest here applicable for undirected graphs? If yes should I only concern about rows? Also, I cannot understand exactly what the `min_max_rows` represents. Is it a vector of values or just the minimal weight of the `maxima_rows`? – J. Doe Jul 05 '18 at 06:41
  • 1) Yes, 2) If and only if your adjacency is symmetric (i.e. not just the upper or lower triangle) then that approach should also work if you only consider the rows. 3) The result is a single value. – Paul Brodersen Jul 05 '18 at 10:13