<< Chapter < Page Chapter >> Page >

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 G ( [link] ):

An exhaustive 2-core enumeration: Ultimately, every induced subgraph is enumerated except those that are not 2-cores.
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.
  1. If G is a minimal k-core, stop, otherwise:
  2. Dissect G as follows:
    1. Find the maximum k-core that is an induced subgraph of G , call it H ( [link] ).
    2. For each vertex v V ( H ) , go to step 1, using for the new G and induced subgraph of H such that V ( G ) = V ( H ) v .

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

  • An algorithm that finds all induced subgraphs in G and then filters k-cores from the rest will trivially enumerate all induced k-cores in 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 , with respect to that subgraph; call this vertex set W 1 . The subgraph may contain vertices that would have degrees less than k if excluding the vertices in W 1 ; call this set W 2 . There may also be vertices dependent on the vertices in W 1 and W 2 to maintain a degree of k ; call those W 3 . We can continue forming these sets until G ( W 1 W 2 . . . W n ) is a k-core for some positive integer n . Define W as ( W 1 V 2 . . . W n )
    • Trivially, take some induced subgraph of G called g . v V ( g ) , D ( v , g ) D ( v , G )
    • Consequently, no induced subgraph of G will contain a k-core including any vertices in W , since no vertex in W has gained degree upon finding an induced subgraph, and, consequently, the collective W still cannot meet the degree threshold to be included in a k-core.
    • Subgraphs are skipped iff they contain vertices in W .

Questions & Answers

what is mutation
Janga Reply
what is a cell
Sifune Reply
how is urine form
Sifune
what is antagonism?
mahase Reply
classification of plants, gymnosperm features.
Linsy Reply
what is the features of gymnosperm
Linsy
how many types of solid did we have
Samuel Reply
what is an ionic bond
Samuel
What is Atoms
Daprince Reply
what is fallopian tube
Merolyn
what is bladder
Merolyn
what's bulbourethral gland
Eduek Reply
urine is formed in the nephron of the renal medulla in the kidney. It starts from filtration, then selective reabsorption and finally secretion
onuoha Reply
State the evolution relation and relevance between endoplasmic reticulum and cytoskeleton as it relates to cell.
Jeremiah
what is heart
Konadu Reply
how is urine formed in human
Konadu
how is urine formed in human
Rahma
what is the diference between a cavity and a canal
Pelagie Reply
what is the causative agent of malaria
Diamond
malaria is caused by an insect called mosquito.
Naomi
Malaria is cause by female anopheles mosquito
Isaac
Malaria is caused by plasmodium Female anopheles mosquitoe is d carrier
Olalekan
a canal is more needed in a root but a cavity is a bad effect
Commander
what are pathogens
Don Reply
In biology, a pathogen (Greek: πάθος pathos "suffering", "passion" and -γενής -genēs "producer of") in the oldest and broadest sense, is anything that can produce disease. A pathogen may also be referred to as an infectious agent, or simply a germ. The term pathogen came into use in the 1880s.[1][2
Zainab
A virus
Commander
Definition of respiration
Muhsin Reply
respiration is the process in which we breath in oxygen and breath out carbon dioxide
Achor
how are lungs work
Commander
where does digestion begins
Achiri Reply
in the mouth
EZEKIEL
what are the functions of follicle stimulating harmones?
Rashima Reply
stimulates the follicle to release the mature ovum into the oviduct
Davonte
what are the functions of Endocrine and pituitary gland
Chinaza
endocrine secrete hormone and regulate body process
Achor
while pituitary gland is an example of endocrine system and it's found in the Brain
Achor
what's biology?
Egbodo Reply
Biology is the study of living organisms, divided into many specialized field that cover their morphology, physiology,anatomy, behaviour,origin and distribution.
Lisah
biology is the study of life.
Alfreda
Biology is the study of how living organisms live and survive in a specific environment
Sifune
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, The art of the pfug. OpenStax CNX. Jun 05, 2013 Download for free at http://cnx.org/content/col10523/1.34
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The art of the pfug' conversation and receive update notifications?

Ask