kl_connected_subgraph#
- kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False)[source]#
Returns the maximum locally
(k, l)
-connected subgraph ofG
.A graph is locally
(k, l)
-connected if for each edge(u, v)
in the graph there are at leastl
edge-disjoint paths of length at mostk
joiningu
tov
.- Parameters:
- GNetworkX graph
The graph in which to find a maximum locally
(k, l)
-connected subgraph.- kinteger
The maximum length of paths to consider. A higher number means a looser connectivity requirement.
- linteger
The number of edge-disjoint paths. A higher number means a stricter connectivity requirement.
- low_memorybool
If this is True, this function uses an algorithm that uses slightly more time but less memory.
- same_as_graphbool
If True then return a tuple of the form
(H, is_same)
, whereH
is the maximum locally(k, l)
-connected subgraph andis_same
is a Boolean representing whetherG
is locally(k, l)
-connected (and hence, whetherH
is simply a copy of the input graphG
).
- Returns:
- NetworkX graph or two-tuple
If
same_as_graph
is True, then this function returns a two-tuple as described above. Otherwise, it returns only the maximum locally(k, l)
-connected subgraph.
See also
References
[1]Chung, Fan and Linyuan Lu. “The Small World Phenomenon in Hybrid Power Law Graphs.” Complex Networks. Springer Berlin Heidelberg, 2004. 89–104.