Graduate Seminar - 4/17, 12:00PM Duncan Hall 1064

Cynthia Wood

"Finding All Minimal K-Cores in Graphs for Modeling K-Assemblies"

We present a recursive algorithm to find all minimal k-cores of a given undirected graph, which belongs to the class of NP-complete problems. The proposed method is a modification of the Bron and Kerbosch algorithm for finding all cliques of an undirected graph. The minimal k-core problem has applications in the area of neuroscience. For example, in the study of associative memory, a cell assembly is a group of neurons that are strongly connected and represent a "concept" of our knowledge. This group is wired in a specific manner such that only a fraction of its neurons will excite the entire assembly. Recent studies have linked the concept of a particular type of cell assembly called k-assembly to the closure of a minimal k-core. Therefore, the proposed method puts us a step closer to test its mathematical definition.