Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » Cell Assembly Enumeration in Random Graphs

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This module is included in aLens by: Digital Scholarship at Rice UniversityAs a part of collection: "The Art of the PFUG"

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

Also in these lenses

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney BurrusAs a part of collection: "The Art of the PFUG"

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.
 

Cell Assembly Enumeration in Random Graphs

Module by: Jordon Cavazos, Khalif Halani, Zachary Rubenstein, Steven J. Cox. E-mail the authors

Summary: This report summarizes work done as part of the Computational Neuroscience PFUG under Rice University's VIGRE program. VIGRE is a program of Vertically Integrated Grants for Research and Education in the Mathematical Sciences under the direction of the National Science Foundation. A PFUG is a group of Postdocs, Faculty, Undergraduates and Graduate students formed round the study of a common problem. This module reproduces the work G. Palm "Towards a Theory of Cell Assemblies". This work was studied in the Rice University VIGRE/REU program in the Summer of 2010. This module builds an algorithm to find cell assemblies by Palm's definition and discusses some preliminary employment of that algorithm.

Introduction

History

Models of individual neurons vary in complexity, but in general, neurons tend to behave like this:

  • A neuron is either excited or not excited.
  • When excited, a neuron will stimulate neurons to which it has an outgoing connection. Otherwise, it will not stimulate other neurons.
  • A neuron becomes excited when it receives a sufficient amount of stimulation from other neurons.

When modeling the brain, see seek to model the collective behavior of neurons. The fundamental type of collective behavior is, by the Donald Hebb model of the brain, the cell assembly.

First introduced by Hebb, the cell assembly is, "a diffuse structure comprising cells... capable of acting briefly as a closed system, delivering facilitation to other such systems and usually having a specific motor facilitation" [4]. A cell assembly is a particular arrangement of a group of neurons with certain properties. The most salient of these properties is that a certain fractional portion of the assembly will excite the entire assembly.

By Hebb's proposal, a cell assembly represents a single concept in the brain. For instance, Hebb proposes that the corner of an abstract triangle may be represented by a cell assembly [4]

Since Hebb first discussed the concept of a cell assembly, there has been some amount of biological research supporting his ideas. For instance, the work of György Buzsáki suggests that groups of cells that fire during a given time period are correlated [2].

Definitions

Figure 1: Node 1 (bright green) has the neighborhood {2, 3, 4, 5} (dark blue)
Figure 1 (exneighbor.png)
Figure 2: A k-core for which k=3
Figure 2 (excore.png)
Figure 3: The process of closure for k=2: in step 2, an arbitrary 3 vertices are activated. Through each subsequent step, those vertices having at least 2 neighbors in the active set are activated in turn. After step 5, there are no more vertices to activate, so the vertices highlighted in step 5. are the closure of the vertices highlighted in step 2.
Figure 3 (excl.png)

Gunther Palm defined Hebb's assembly in the concrete language of graph theory [6]. In brief, Palm's discussion constructs, or depends upon, the following definitions:

  • graph: A graph GG has a vertex set, V(G),V(G), and a set of edges, E(G)V(G)×V(G).E(G)V(G)×V(G). If u,vV(G)u,vV(G) and uvE(G),uvE(G), we say that the graph GG has an edge directed from the vertex uu toward the vertex v.v. Vertices are labeled with integers by convention.
  • neighborhood: We define the neighborhood of some vertex vV(G)vV(G) with respect to G,G, call it N(v,G),N(v,G), as {u:uvE(G)}{u:uvE(G)} (Figure 1).
  • degree: The degree of a vertex vV(G)vV(G) with respect to G,G, call it D(v,G),D(v,G), is |N(v,G)|.|N(v,G)|.
  • subgraph: A graph gg is a subgraph of GG iff V(g)V(G)V(g)V(G) and E(g)E(G).E(g)E(G). Further, gg is an induced subgraph of GG iff gg is a subgraph of GG and eE(G)(V(g)×V(g)),eE(g).eE(G)(V(g)×V(g)),eE(g).
  • k-core: A subgraph gg of GG is a kk-core iff vV(g),|X|k,vV(g),|X|k, where X=N(v)V(g)X=N(v)V(g) (Figure 2).
  • minimal k-core A subgraph gg of GG is a minimal k-core iff it has no induced subgraphs which are k-cores.
  • maximum k-core A subgraph gg of GG is a maximum k-core iff GG contains no k-cores hh for which the |V(h)|>|V(g)|.|V(h)|>|V(g)|.
  • activation: We say that a vertex vV(G)vV(G) can be either active or inactive. We generally say that, initially, an arbitrary subset of vertices MV(G)MV(G) are active and the rest inactive. We further define a map fk(M,G):(setsofvertices,graphs)(setsofvertices)fk(M,G):(setsofvertices,graphs)(setsofvertices) which performs the following operation:
    • Take a graph G,G, and a set of vertices, M,M, where MV(G).MV(G).
    • vV(G)vV(G):
      • let Y=MN(v,G)Y=MN(v,G)
      • iff |Y|k,|Y|k, then vRvR
    • Return R.R.
    For convenience, we add a superscript fkn(M,G),fkn(M,G), where fk2(M,G)=fk(fk(M,G),G),fk3(M,G)=fk(fk(fk(M,G),G),G),fk2(M,G)=fk(fk(M,G),G),fk3(M,G)=fk(fk(fk(M,G),G),G), etc.
  • closure: We say that the closure of a set of active nodes MM with respect to the graph G,G, call it clk(M,G)clk(M,G), is equal to fk(M,G).fk(M,G). If fkn(M,G)fkn(M,G) does not converge for some sufficiently large n,n, then the closure of MM is undefined (Figure 3).
  • k-tight: A k-core T,T, which is an induced subgraph of G,G, is k-tight iff it satisfies the following condition:
    • KK where KK is an induced subgraph of TT and a k-core:
      • cl(V(K),G)V(T),cl(V(K),G)V(T), or,
      • cl(V(T)V(K),G)=cl(V(T)V(K),G)=
  • k-assembly: An induced subgraph AA of GG is a k-assembly iff V(A)=cl(V(T),G)V(A)=cl(V(T),G) where TT is a k-tight induced subgraph of G.G.

Goal

We seek to understand Palm's definition of cell assembly in context. In particular, we seek to determine whether a brain-sized random graph can contain a realistic number of assemblies by Palm's definition.

In this report, we describe the process of k-assembly enumeration and explain some preliminary experimentation using that algorithm.

The report exists in two forms. The abridged version includes the material described above, while the full version goes on to include more trend examples, an extensive collection of visual examples of k-Assemblies, and implementation.

This is the abridged version. The full version is available here.

Finding k-Assemblies

Finding k-assemblies takes place in two steps: k-core enumeration and k-assembly confirmation:

k-Core Enumeration

The process of k-Core enumeration follows the general form of a branch and bound algorithm. That is, it follows the process:

  1. If possible, solve the problem, otherwise:
  2. Break the problem into several smaller problems, for each of these smaller problems, go to step 1.

Applied to our problem, the general algorithm looks like this, given some input graph GG (Figure 4):

Figure 4: An exhaustive 2-core enumeration: Ultimately, every induced subgraph is enumerated except those that are not 2-cores.
Figure 4 (branchsm.png)
Figure 5: The maximum k-core algorithm for a 3-core: 1,2) A vertex is eliminated from the graph, leaving an induced subgraph which is not a minimal 3-core. 3,4) All vertices which have insufficient degree with respect to the new subgraph graph (less than 3 in this case) are eliminated. 5,6) Again, a vertex without sufficient degree is eliminated. The subgraph pictured in step 6 has no vertices of less than k degree, so the process is completed.
Figure 5 (maxcoresm.png)
  1. If GG is a minimal k-core, stop, otherwise:
  2. Dissect GG as follows:
    1. Find the maximum k-core that is an induced subgraph of G,G, call it HH (Figure 5).
    2. For each vertex vV(H),vV(H), go to step 1, using for the new GG and induced subgraph of HH such that V(G)=V(H)v.V(G)=V(H)v.

This process finds all k-cores in the original G.G. To sketch a proof:

  • An algorithm that finds all induced subgraphs in GG and then filters k-cores from the rest will trivially enumerate all induced k-cores in G.G.
  • The k-core enumeration algorithm described is equivalent to such an algorithm. By in turn eliminating every vertex from a graph, the algorithm find all induced subgraphs except for those it skips. The skipped subgraphs will never generate k-cores not already generated:
    • Skipped subgraphs have at least one vertex of degree less than k,k, with respect to that subgraph; call this vertex set W1.W1. The subgraph may contain vertices that would have degrees less than kk if excluding the vertices in W1;W1; call this set W2.W2. There may also be vertices dependent on the vertices in W1W1 and W2W2 to maintain a degree of kk; call those W3.W3. We can continue forming these sets until G(W1W2...Wn)G(W1W2...Wn) is a k-core for some positive integer n.n. Define WW as (W1V2...Wn)(W1V2...Wn)
    • Trivially, take some induced subgraph of GG called g.vV(g),D(v,g)D(v,G)g.vV(g),D(v,g)D(v,G)
    • Consequently, no induced subgraph of GG will contain a k-core including any vertices in W,W, since no vertex in WW has gained degree upon finding an induced subgraph, and, consequently, the collective WW still cannot meet the degree threshold to be included in a k-core.
    • Subgraphs are skipped iff they contain vertices in W.W.

Complexity

The algorithm described above runs in approximately exponential (O(n!))(O(n!)) time, which is to be expected since it solves an NP-hard problem.

Figure 6: A clique for which k=4k=4
Figure 6 (exclique.png)

The enumeration of k-cores reduces to the NP complete clique problem [5] as follows:

  • A clique is a k-core for which the number of vertices in the core is equal to k+1k+1 (Figure 6).
  • The clique problem is: determine whether an arbitrary graph contains a clique of at least size n.n.
  • If we could accomplish k-core enumeration in polynomial time, say O(nk),O(nk), where nn is the number of nodes in the graph, then:
    • We could find cores of all kk in, at most, O(n×nk)=O(nk+1)O(n×nk)=O(nk+1) time, because there is no kk core in a given graph for which kk exceeds n.n.
    • Without increasing fundamental run-time, we could flag each of those k-cores which is a clique. In doing so, we find all cliques.
    • By simply finding the largest of this group of cliques, we have solved the clique problem in polynomial time.

Consequently, k-core enumeration belongs to the class of NP-hard problems, meaning that it is not clear whether an algorithm that runs significantly faster than exponential time can be devised.

That is not to say, however, that the algorithm cannot be improved upon at all. For instance, one of our implementations takes advantage of the fact that, if we form an induced subgraph HH by removing some vertex vv from a graph G,G, if vv is not in a k-core, then the graph II resulting from removing any of vv's neighbors that are not in a k-core from GG will have the same maximum k-core as H.H. Also, our algorithm takes care not to revisit previously enumerated branches. Different approaches can certainly speed up an algorithm to solve the problem, but it is not clear that any approach will make the algorithm run in sub-exponential time.

Assembly Enumeration

Figure 7: k-Assembly enumeration on a reduced set of k-cores.
Figure 7 (assemblyDiagram2.png)

Upon enumerating all k-cores, every unique closure of a k-core is analyzed to determine whether any one of the k-cores that closes to that closure is tight (Figure 7). Checking tightness involves nothing more clever than simply verifying the above definition of tight. If at least one of the cores that closes to a given closure is tight, then that closure is a collected into the set of k-assemblies, otherwise, it is ignored.

Experimentation

After devising an algorithm to find every k-assembly, we attempted to discover attributes about k-assemblies through, first, generating random graphs, and then, enumerating the assemblies contained in those graphs.

Random Graph Generation

We employed two primary types of random graphs.

Figure 8: A Bernoulli random graph
Figure 8 (exbor.png)
Figure 9: A scale-free Cooper-Frieze random graph
Figure 9 (excf.png)
  1. The classical Bernoulli random graph (Figure 8):
    • Pick some probability p,p, and a number of vertices, n.n. Create a graph G,G, for which V(G)=1,2,...n.V(G)=1,2,...n.
    • For all pairs of vertices, (i,j),(i,j), where ijij and 0<i,jn,0<i,jn, an edge ijE(G)ijE(G) with probability p.p.
  2. The scale-free Cooper-Frieze random graph (Figure 9) [1]. As we implement it:
    • pick some positive integer TT; α,β,γ,δ[0,1]α,β,γ,δ[0,1]; P,Q,P,Q, which are 1-indexed lists. P=(p1,p2,...,pn),P=(p1,p2,...,pn), where i=1np=1,i=1np=1, and pi[0,1]i{1,2,...,n}.pi[0,1]i{1,2,...,n}.Q=(q1,q2,...,qm),Q=(q1,q2,...,qm), where i=1mq=1,i=1mq=1, and pi[0,1]i{1,2,...,m}.pi[0,1]i{1,2,...,m}.
    • Begin with a graph G,G, where V(G)={1},V(G)={1}, and E(G)={11}.E(G)={11}. (That is, G is a graph with a single vertex which has a single edge connected to itself).
    • t{0,1,2,...,T}:t{0,1,2,...,T}:
      • Do the "Old" procedure with probability α,α, otherwise, do the procedure "New."
      • Do the procedure "Add Edges."
    • Old:
      • with probability δ,δ, choose the vertex startstart from among the set of vertices in V(G)V(G) randomly, giving each vertex an even chance. Otherwise, choose startstart with the probability for each vertex proportional to the the degree of that vertex with respect to G.
      • with probability γγ set the boolean variable terminateUniformlyterminateUniformly to true.true. Otherwise, set the variable to false.false.
      • choose an index of QQ so that the index ii has a probability qiqi of being chosen. Set the integer variable numberOfEdgesnumberOfEdges to this chosen index.
    • New:
      • Add a new vertex vv to V(G).V(G). Call that vertex start.start.
      • With probability ββ set the boolean variable terminateUniformlyterminateUniformly to true.true. Otherwise, set the variable to false.false.
      • choose an index of PP so that the index ii has a probability pipi of being chosen. Set the integer variable numberOfEdgesnumberOfEdges to this chosen index.
    • Add Edges:
      • Create the set ENDEND by choosing numberOfEdgesnumberOfEdges vertices from G.G. The vertices are chosen randomly, either with uniform probability if terminateUniformlyterminateUniformly is true,true, or in proportion to degree otherwise.
      • vertices eEND,eEND, add to GG an edge directed from startstart to e.e.

It should be noted that throughout the book, only scale-free graphs are allowed either:

  • Edges with weights greater than 1 (That is, there may exist more than one edge uvE(G)uvE(G) where uu and vv are vertices in V(G).V(G).)
  • "Loops" which connect nodes to themselves (That is, edges of the form uu.uu.)

We allow these exceptions so that our graphs will be in full compliance with the Cooper-Frieze model.

Data

After generating a number of random graphs, we investigated a number of relationships between cell assemblies vs. other features in random graphs. We speculate on a few of these relationships here.

When we vary the probability that any given pair of vertices has an edge between them over a number of undirected, Bernoulli random graphs, we can see a number of distinct phases in the number of cell assemblies that these graphs will have, on average (Figure 10).

Figure 10: Bernoulli random graphs appear to undergo phase changes when varying edge probability
Figure 10 (Assembly_enum11,3.png)

First, edge probability is insufficient to form even one assembly, then the number of assemblies increases to a peak as the graph becomes more dense. Past that peak, the closure of all tight sets converges to a single cell assembly. It would be interesting to find a method for predicting the probability at which this peak occurs, and then comparing that value to biology.

The Cooper-Frieze scale-free graph has no parameter to directly adjust edge density, but varying the related parameter, α,α, does have similar effects.

A fairly promising, although ostensibly not very accurate, indicator of the number of k-cores is the maximum eigenvalue of a graph's adjacency matrix (Figure 11).

Figure 11: Maximum eigenvalues apparently have a positive correlation with number of assemblies in a Bernoulli random graph. (r=0.7309)(r=0.7309)
Figure 11 (Eig_Core_Comparea.png)

On undirected Bernoulli random graphs, the two variables appear to have a nontrivial, positive correlation. However, here we see that the method of graph construction is extremely important to any such observations, since on directed scale-free graphs, we see a relationship that is not nearly as clear (Figure 12).

Figure 12: For Cooper-Frieze random graphs, this correlation is much more dubious. (r=-0.1315)(r=-0.1315)
Figure 12 (Eig_Core_Compareb.png)

Future Work

  • On commodity hardware, the k-core enumeration algorithm terminates in a few minutes on graphs on the order of 10 nodes. It can process larger graphs given a low density of edges or a large k. Consequently, it is not clear that strict enumeration will be useful on human-brain-sized graphs with approximately 100 billion neurons and 1000 connections per neuron, but it may be useful for smaller graphs. For instance, a honey bee has fewer than 1 million neurons [3].
  • If strict enumeration fails even in smaller cases, it would perhaps be possible to take advantage of certain knowledge about the structure of brains in order to speed up enumeration by restricting the types of graphs that need to be enumerated. For instance, if we could safely use a bipartite model for a brain, the algorithm could likely be optimized for bipartite graphs.
  • Also, cell assembly enumeration could proceed further from a statistical standpoint, as hinted at in the "Data" section. Perhaps some function could be devised that maps some more easily discerned information about a graph to the probability that that graph will contain a given number of cell assemblies.
  • The definition of cell assemblies, as presented here, is fairly cumbersome. If certain aspects of the definition, such as closure, could be simplified, perhaps an easier approach to cell assemblies may become apparent.
  • Cell assemblies should theoretically have far more function than simply existing as static structures in random graphs. Studying the interaction of cell assemblies and the learning processes that create cell assemblies may yield interesting insights into neuroscience in general.

Conclusion

Our approach to enumeration of cell assemblies in arbitrary graphs probably runs insufficiently fast to explore the problem as an end in itself. However, it does give us a useful tool to help us understand cell assemblies. We can now find an unlimited number of examples of cell assemblies which we may use as tools to explore general trends and gain insight into the structure of cell assemblies. Perhaps with enough work on the subject, we may find a viable way to understand the workings of the brain through random graph theory.

References

  1. Bollobás, Béla and Riordan, Oliver. (2003). Mathematical Results on Scale-free Random Graphs. In Handbook of Graphs and Networks: From the Genome to the Internet. (pp. 1-32). Weinheim: Wiley.
  2. Buzsáki, György. (2006). Rhythms of the Brain. Oxford University Press.
  3. Chudler, Eric H. Brain Facts and Figures. [Retrieved 21 Jul 2010]. http://faculty.washington.edu/chudler/facts.html.
  4. Hebb, D. O. (1949). The Organization of Behavior. Mahwah: Lawrence Erlbaum Associates.
  5. Karp, Richard M. and Miller, Raymond E. and Thatcher, James W. (1975). Reducibility Among Combinatorial Problems. The Journal of Symbolic Logic, 40(4), 85-103.
  6. Palm, Gunther. (1981). Towards a Theory of Cell Assemblies. Biological Cybernetics, 39, 181-194.

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks