Condition number, Erdos-Renyi model

Вычисление числа обусловленности матрицы

import numpy as np
import networkx as nx
import scipy as sp
import timeit as ti
from scipy import stats as stc

Генераторы для создания графа Эрдоша-Реньи $G(n,p)$, где $n$-число вершин, $p$-вероятность возникновения ребра между любыми вершинами графа

https://networkx.org/documentation/stable/reference/generators.html#module-networkx.generators.random_graphs

Списки смежности графа https://networkx.org/documentation/stable/reference/readwrite/adjlist.html

Для записи в файл и чтения из файла используются read_adjlist, write_adjlist

# Пример вычисления числа обусловленности 
# graph = nx.erdos_renyi_graph(n=10, p=0.5)
# n=10
G=nx.read_adjlist("test_10.txt", create_using=nx.Graph(), nodetype=int)
print(nx.info(G))
print("is connected = " , nx.is_connected(G))

Name: 
Type: Graph
Number of nodes: 10
Number of edges: 25
Average degree:   5.0000
is connected =  True

%matplotlib notebook
# Визуализация графа
nx.draw(G, pos=nx.circular_layout(G))

Стандартный алгоритм вычисления cond(LG) для Лапласиана

# вычисление Лапласиана
LG = nx.laplacian_matrix(G)
type(LG)

scipy.sparse.csr.csr_matrix

# т.к. det(LG)=0
L1=LG[0:(len(G)-1),0:(len(G)-1)]

# преобразовать в массив
LG_ndarray=L1.toarray()

# 1 вариант (с помощью .cond)
print("cond. number = ", np.linalg.cond(LG_ndarray))

cond. number =  14.386733454016102

# 2 вариант (с помощью svd)
u, s, vh = np.linalg.svd(LG_ndarray)
s

array([8.42755334, 7.42994198, 6.        , 5.23181935, 5.        ,
       4.19082305, 3.71986229, 3.41421356, 0.58578644])

s[0]/s[8]

14.386733454016126

Алгоритм на разреженной структуре

https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.svds.html

# 3 вариант (с помощью sp.sparse)
U, S_l, V = sp.sparse.linalg.svds(L1.asfptype(),k=1,which='LM')
print(S_l)
U, S_s, V = sp.sparse.linalg.svds(L1.asfptype(),k=1,which='SM')
print(S_l[0]/S_s[0])

[8.42755334]
14.386733454015978