Re: [igraph] max min degree of a graph

[Pagliari, Roberto]

Hi Tamas,
Yes, that's what I thought. I will manually iterate then. 

Thank you,


-----Original Message-----
From: Tamás Nepusz [mailto:address@hidden 
Sent: Tuesday, July 29, 2014 3:37 PM
To: Help for igraph users; Pagliari, Roberto
Subject: RE: [igraph] max min degree of a graph

> how should I change the lines below for an undirected graph with 
> weights (so that max min \sum weight should be optimized)?
You can't; coreness() works on unweighted graphs only, and there is no concept 
for "weighted" coreness in igraph. You might be able to find a solution by 
iteratively removing the vertices with the lowest weighted degree. The idea 
here is as follows. Suppose that the smallest weighted degree in your original 
(unmodified) graph is w. This means that the maximum of the minimum weighted 
degree must be at least w because you already have an example (your original 
graph) where the minimum weighted degree is w. If there is any subgraph in your 
graph that has a minimum weighted degree higher than w, then this must not 
include any vertex that has weighted degree w (or smaller), so you can safely 
remove any vertex in your graph where the minimum weighted degree is w. Now you 
have a subgraph of your original graph, where you can start the same reasoning 
from scratch. Eventually you will end up in a situation where removing any of 
your vertices from the graph would decrease the minimum weighted degree _after_ 
the removal -- this is where you can terminate the algorithm and reiterate over 
the subgraphs you have found before to see which one had the highest minimum 
degree.

T.