written by Eric J. Ma on 2019-06-15 | tags: graphs network science data science
The connection between graphs and linear algebra is profound and deep. I learned that lesson yet again. Come read more about it!
Once again, I’m reminded through my research how neat and useful it is to be able to think of matrices as graphs and vice-versa.
I was constructing a symmetric square matrix of values, in which multiple cells of the matrix were empty (i.e. no values present). (Thankfully, the diagonal is guaranteed dense.) From this matrix, I wanted the largest set of rows/columns that formed a symmetric, densely populated square matrix of values, subject to a second constraint that the set of rows/columns also maximally intersected with another set of items.
Having thought about the requirements of the problem,
my prior experience with graphs reminded me that
every graph has a corresponding adjacency matrix,
and that finding the densest symmetric subset of entries in the matrix
was equivalent to finding cliques in a graph!
My intern and I proceeded to convert the matrix into its graph representation,
and a few API calls in networkx later, we found the matrix we needed.
The key takeaway from this experience? Finding the right representation for a problem, we can computationally solve them quickly by using the appropriate APIs!
@article{
ericmjl-2019-graphs-matrices,
author = {Eric J. Ma},
title = {Graphs and Matrices},
year = {2019},
month = {06},
day = {15},
howpublished = {\url{https://ericmjl.github.io}},
journal = {Eric J. Ma's Blog},
url = {https://ericmjl.github.io/blog/2019/6/15/graphs-and-matrices},
}
I send out a newsletter with tips and tools for data scientists. Come check it out at Substack.
If you would like to sponsor the coffee that goes into making my posts, please consider GitHub Sponsors!
Finally, I do free 30-minute GenAI strategy calls for teams that are looking to leverage GenAI for maximum impact. Consider booking a call on Calendly if you're interested!