<jupyter_start><jupyter_text>Spectral analysis with numpyNumpy has a submodule for the spectral analysis.<jupyter_code>from numpy import linalg as la<jupyter_output><empty_output><jupyter_text>Get the adjacency matrix of the Florentine families ![](../Images/ff_network.png)<jupyter_code>with open('../Data/florentine_families.dat', 'r') as file:
    all_file=file.readlines()
families=np.array(all_file[4:20])
ff_adj=np.genfromtxt('../Data/florentine_families.dat', skip_header=41, dtype='i8')[:16]
ff_adj.shape
np.all(ff_adj.T==ff_adj)
del file, all_file<jupyter_output><empty_output><jupyter_text>Eigenvalues and eigenvectors For real symmetric or Hermitian matrices use eigh. The first output is the array of eigenvalues (sorted), the second is an array of eigenvectors, in the same order.<jupyter_code>cacca=la.eigh(ff_adj)
len(cacca)
len(cacca[0])
cacca[1].shape<jupyter_output><empty_output><jupyter_text>**Pay attention!** Eigenvectors are the columns!<jupyter_code>ff_eigens=la.eigh(ff_adj)
del cacca<jupyter_output><empty_output><jupyter_text>Perron - Frobenius and connected components<jupyter_code>np.all(ff_adj>=0)<jupyter_output><empty_output><jupyter_text>The adjacency matrix is non negative (ok, that's easy)<jupyter_code>np.unique(ff_eigens[0], return_counts=True)<jupyter_output><empty_output><jupyter_text>$\Rightarrow$ All eigenvalues have multiplicity 1, thus the greatest eigenvalue has.<jupyter_code>ff_eigens[0][-1]>-ff_eigens[0][0]<jupyter_output><empty_output><jupyter_text>$\lambda>|\mu|,\,\forall\mu\in\sigma(A)$<jupyter_code>ff_eigens[0][-1]
ff_eigens[1][:,-1]
ff_eigens[1][:, -1]>0<jupyter_output><empty_output><jupyter_text>D'oh! So, what should we conclude?<jupyter_code>ff_k=np.sum(ff_adj, axis=1)
print(ff_k)<jupyter_output>[1 3 2 3 3 1 4 1 6 1 3 0 3 2 4 3]<jupyter_text>A-HA! We got an isolated node!<jupyter_code>np.where(ff_k==0)
where_iso=np.where(ff_k==0)[0][0]
families[where_iso]<jupyter_output><empty_output><jupyter_text>None got married with the Pucci family! Actually this information was sort of hidden:<jupyter_code>ff_eigens[0]<jupyter_output><empty_output><jupyter_text>$10^{-17}$ is actually zero (due to the finite machine precision it is different from zero, but it means zero). np.finfo returns the machine limits for a certain data type<jupyter_code>np.finfo(np.float64).eps<jupyter_output><empty_output><jupyter_text>Let's try again, after removing the isolated node.  PF again  Pucci Mask and checks<jupyter_code>pucci_mask=np.ones(len(ff_k), dtype='bool')
pucci_mask
pucci_mask[where_iso]=False
pucci_mask
ff_new_families=families[pucci_mask]
ff_new_adj=ff_adj[pucci_mask]
ff_new_adj.shape
ff_new_adj=ff_new_adj.T[pucci_mask]
ff_new_adj.shape<jupyter_output><empty_output><jupyter_text>Check!<jupyter_code>ff_new_k=np.sum(ff_new_adj, axis=1)
print(ff_new_k)
np.all(np.dot(ff_new_adj,np.dot(ff_new_adj,np.dot(ff_new_adj,np.dot(ff_new_adj,np.dot(ff_new_adj,ff_new_adj)))))>0)<jupyter_output><empty_output><jupyter_text>Let's try again Ok, let's try again. The non-negativity is ok, since we just remove a row and a column filled with zeros. The same is true for the multiplicity (we removed the zero eigenvalue), but let's check.<jupyter_code>np.all(ff_new_adj>=0)
ff_new_eigens=la.eigh(ff_new_adj)
ff_new_eigens[0]
np.unique(ff_new_eigens[0], return_counts=True)<jupyter_output><empty_output><jupyter_text>Nothing should change even for the 2nd implication of the PF-theorem...<jupyter_code>ff_new_eigens[0][-1]>-ff_new_eigens[0][0]
ff_new_eigens[1][:,-1]
np.all(ff_new_eigens[1][:,-1]>0)<jupyter_output><empty_output><jupyter_text>![](../Images/l4_turk.gif)  Exercise: show that the Perron-Frobenius hypotheses are valid for the Zachary dataset  Exercise: show that the (undirected) network represented by the edge ../Data/mysterious_dataset.txt is bipartite<jupyter_code>roy=np.genfromtxt('../Data/mysterious_dataset.txt', dtype='i8')
len_matrix=np.max(roy)+1
matrix=np.zeros((len_matrix,len_matrix))
for r in roy:
    matrix[r[0], r[1]]=1
    matrix[r[1], r[0]]=1
np.all(matrix==matrix.T)
la.eigh(matrix)<jupyter_output><empty_output><jupyter_text>Laplacian Go back to the Medici family. Let's forget about Pucci and go to the Laplacian:<jupyter_code>ff_new_L=np.diag(ff_new_k)-ff_new_adj
ff_new_L
ff_new_L_eigens=la.eigh(ff_new_L)<jupyter_output><empty_output><jupyter_text>Some checks:<jupyter_code>np.all(ff_new_L_eigens[0]>=0)
ff_new_L_eigens[0][0]<jupyter_output><empty_output><jupyter_text>The smallest eigenvalue is actually zero.<jupyter_code>ff_new_L_eigens[0][-1]
np.max(ff_k)<jupyter_output><empty_output><jupyter_text>Thus the greatest eigenvalue is greater than the greatest degree!<jupyter_code>ff_new_L_eigens[0][1]<jupyter_output><empty_output><jupyter_text>The network is connected!  Exercise: define a function that calculates the Laplacian  Exercise: show that the Zachary network is connected  Fiedler vector Consider the Fiedler vector with $r=0$ and consider the relative partitions.<jupyter_code>group_0=np.where(ff_new_L_eigens[1][:, 1]>=0)[0]
group_1=np.where(ff_new_L_eigens[1][:, 1]<0)[0]
print(ff_new_families[group_0])
print(ff_new_families[group_1])<jupyter_output>['ALBIZZI\n' 'BARBADORI\n' 'BISCHERI\n' 'CASTELLAN\n' 'GINORI\n'
 'GUADAGNI\n' 'LAMBERTES\n' 'PERUZZI\n' 'RIDOLFI\n' 'STROZZI\n'
 'TORNABUON\n']
['ACCIAIUOL\n' 'MEDICI\n' 'PAZZI\n' 'SALVIATI\n']<jupyter_text>What happens reapplying Fiedler partition to the previous partition?  group_0<jupyter_code>ff_new_adj_0=ff_new_adj[group_0].T
ff_new_adj_0=ff_new_adj_0[group_0]<jupyter_output><empty_output><jupyter_text>Check!<jupyter_code>ff_new_adj_0.shape
len(group_0)
np.all(ff_new_adj_0.T==ff_new_adj_0)
np.sum(ff_new_adj_0, axis=0)
ff_new_families_0=ff_new_families[group_0]
def laplacianer(adj):
    deg=np.sum(adj, axis=1)
    return np.diag(deg)-adj
ff_new_L_0=laplacianer(ff_new_adj_0)
ff_new_L_0_eigens=la.eigh(ff_new_L_0)
ff_new_L_0_eigens[0]<jupyter_output><empty_output><jupyter_text>This cluster is connected.<jupyter_code>group_0_0=np.where(ff_new_L_0_eigens[1][:, 1]>=0)[0]
group_0_1=np.where(ff_new_L_0_eigens[1][:, 1]<0)[0]
ff_new_families_0
print(ff_new_families_0[group_0_0])
print(ff_new_families_0[group_0_1])<jupyter_output>['ALBIZZI\n' 'GINORI\n' 'GUADAGNI\n' 'LAMBERTES\n' 'TORNABUON\n']
['BARBADORI\n' 'BISCHERI\n' 'CASTELLAN\n' 'PERUZZI\n' 'RIDOLFI\n'
 'STROZZI\n']<jupyter_text>group_1<jupyter_code>ff_new_adj_1=ff_new_adj[group_1].T
ff_new_adj_1=ff_new_adj_1[group_1]<jupyter_output><empty_output><jupyter_text>Check!<jupyter_code>ff_new_adj_1.shape
len(group_1)
np.all(ff_new_adj_1.T==ff_new_adj_1)
np.sum(ff_new_adj_1, axis=0)
ff_new_families_1=ff_new_families[group_1]
ff_new_L_1=laplacianer(ff_new_adj_1)
ff_new_L_1_eigens=la.eigh(ff_new_L_1)
ff_new_L_1_eigens[0]<jupyter_output><empty_output><jupyter_text>This cluster is connected.<jupyter_code>group_1_0=np.where(ff_new_L_1_eigens[1][:, 1]>=0)[0]
group_1_1=np.where(ff_new_L_1_eigens[1][:, 1]<0)[0]
ff_new_families_1
print(ff_new_families_1[group_1_0])
print(ff_new_families_1[group_1_1])<jupyter_output>['ACCIAIUOL\n' 'MEDICI\n']
['PAZZI\n' 'SALVIATI\n']
{'fraction_non_alphanumeric': 0.13626745662293693, 'fraction_numerical': 0.025391451544646636, 'mean_word_length': 10.130298273155416, 'pattern_counts': {'":': 0, '<': 112, '<?xml version=': 0, '>': 121, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '28', 'dir': 'jupyter-structured-clean-dedup', 'id': '311954', 'license': 'MIT', 'n_tokens_mistral': 3225, 'n_tokens_neox': 3040, 'n_words': 439, 'path': 'Lectures/Lecture_5_Numpy_Spectra.ipynb', 'repo_name': 'fabiosaracco/networks_01_2020', 'size': '7089'}