Exploring K-Dense Graphs Within Graph Theoretical Analysis
Samuel P. Prahlow, Ralucca Gera, Henry Escuadro, Linda Eroh, Steven J. Winters · ValpoScholar (Valparaiso University) · 2014
Due to the increasing implementation and discovery of networks within all disciplines of life, the study of connectivity, specifically sub-graphs within these larger networks, has become increasingly important. Network theory has been helpful in cancer research, finding an efficient business model, and developing comprehensive security measures. Motivated by the idea of community (or sub-graph) detection within complex networks, we focused on finding characterizations of k-dense communities. We present some initial results about the equivalency between k-clique, k-dense, and k-core sub-graphs when the number of vertices equals the k value. Success by others in characterizing k-cliques and k-core led us to examine patterns in k-dense. We show several graphic progressions and tables which suggest potential formulas, and possible generalization to a minimum edge construction for any k-dense graph. Continuing this research has implications for being able to better understand and distinguish the k-dense sub-graphs, which in turn would help in the study of the connectivity and characterizations of the larger graph/network in the real world.