# vertex.sort: Elucidates the hierarchical structure of a directed network... In VertexSort: Network Hierarchical Structure and Randomization

## Description

The `vertex.sort()` function applies a network decomposition algorithm called the Vertex Sort to a directed network (Jothi et al. 2009) and generates an object of class vertex.sort. The Vertex Sort algorithm elucidates the hierarchical structure of a directed network by classifying its nodes into mainly four layers: the Top, Core, Bottom and Zero layers. For more information on each of these layers see details below or refer to (Jothi et al. 2009).

## Usage

 ```1 2 3 4 5``` ``` vertex.sort(edges) ## S3 method for class 'vertex.sort' print(x, ...) ## S3 method for class 'vertex.sort' summary(object, ...) ```

## Arguments

 `edges` a dataframe that contains a symbolic edge list of the graph to decompose. It should contain two columns listing Actor and Target nodes, see details below. `x, object` the vertex.sort object of wich details or summary will be printed. `...` further arguments passed to or from other methods.

## Details

The Vertex Sort algorithm is a network decomposition method that elucidates the network hierarchy (Jothi et al. 2009). It classifies network nodes into various levels. First, it transforms the directed network into an acyclic directed graph. Second, it applies the leaf removal (LR) algorithm on the network and on its transpose. Third, it merges the results of the two LR applications into a global result, in which the level of each node is determined by the possibility of a node to span many levels. Finally, it groups nodes into four non-overlapping layers: the Top, Core, Bottom and Zero layers. The Core layer is made of the nodes composing the biggest strongly connected component of the network and Top and Bottom layers contain nodes that regulate and are regulated by the Core layer respectively. Transforming a network from a cyclic to an acyclic graph is achieved by collapsing each strongly connected component into a super-node.

The `print()` function prints the details of a vertex.sort object (i.e. all the elements of the vertex.sort object).

The `summary()` function prints a summary of a vertex.sort object. It describes: the sorted graph (i.e. number of nodes, edges, layers and levels), the graph layers (i.e. number of nodes of type Actors in Top, Core and Bottom layers and the number of nodes of type Targets), and the number of excluded and disconnected nodes (i.e. number of excluded Actor nodes and the number of disconnected Actor and Target nodes).

## Value

The `vertex.sort()` function returns an object of class vertex.sort. The functions `print()` and `summary()` are used to obtain the details and a summary of the contents of the vertex.sort objet.

An object of class vertex.sort is a list containing the following elements:

 `graph` a graph of class `igraph` containing the edges of the input network to be sorted. `edges` a dataframe containing the network edges `traits` a dataframe listing the network nodes and determining whether each of them is of type Actor (node with a non-zero out-degree) or of type Target (a node with a zero out-degree or a node that does not regulate an Actor node). `actors` a vector containing all Actor nodes. `targets` a vector containing all Target nodes. `top.actors` a vector containing Actor nodes that were classified in the Top layer. `core.actors` a vector containing Actor nodes that were classified in the Core layer. `bottom.actors` a vector containing Actor nodes that were classified in the Bottom layer. `excluded.actors` a vector containing Actor nodes that were excluded from the classification, because the algorithm was unable to classify them propertly. `disconnected.actors` a vector containing Actor nodes that were found to be disconnected from the input graph and hence were not subject to the Vertex Sort algorithm. `disconnected.targets` a vector containing Target nodes that were found to be disconnected from the input graph and hence were not subject to the decomposition algorithm. `levels.no` an integer indicating the number of levels of the sorted network. `nodes.in.levels` a list enumerating the nodes belonging to each level.

## Note

In the article (Jothi et al. 2009), the authors talked about only three layers (the Top, Core and Bottom layers). However, in the present package we talk about four layers, the three layers mentioned by Jothi et al. in addition to the Zero layer corresponding to the layer containg the target nodes that do not regulate other Actor nodes.

## Author(s)

Diala Abd-Rabbo diala.abd.rabbo@gmail.com

## References

Jothi, R., Balaj, S., Wuster, A. et al. 2009 Molecular system biology 5, –294-309.

## Examples

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` ``` ## load the VertexSort library library(VertexSort) ## load interactions of the kinase-phosphatase network (kp-net) data("interactions") ## apply the Vertex Sort algorithm vs_kp_net <- vertex.sort(interactions) ## print the results (the contents of the vertex.sort object) vs_kp_net ## print a summary of the results summary(vs_kp_net) ## print levels.no, an element of the vertex.sort object vs_kp_net\$levels.no ```

### Example output

```Loading required package: igraph

Attaching package: 'igraph'

The following objects are masked from 'package:stats':

decompose, spectrum

The following object is masked from 'package:base':

union

Call:
vertex.sort(edges = interactions)

graph:
IGRAPH 17429be DN-B 616 1087 --
+ attr: name (v/n), id (v/n), orf (v/c), type (v/c), level (v/n), layer
| (v/c)
+ edges from 17429be (vertex names):
[1]  1->129  1->130  1->131  1->132  2->  2  2-> 40  2->133  2->134  3->135
[10]  3-> 19  3->136  3->137  3->138  3->139  3->140  3->141  3->142  3->143
[19]  3->144  3->145  3->146  4-> 10  5->147  5->148  5-> 16  5->149  5->150
[28]  5->151  5->152  6->153  6->154  6->119  6->155  7->156  7->157  7->158
[37]  8->  8  9->147  9->159  9->160  9-> 16  9->149  9->161  9->162  9->163
[46]  9->164  9->165  9->166  9->167  9->151  9->152  9->102  9->168 10->169
[55] 10->170 10->171 10->172 10->173 10->174 10->175 10->  2 10->176 10->177
+ ... omitted several edges

Top layer:
[1] "YBL056W" "YBL088C" "YBR125C" "YBR136W" "YCR073C" "YCR091W" "YDL006W"
[8] "YDL047W" "YDL079C" "YDL134C" "YDL188C" "YDR075W" "YDR436W" "YDR490C"
[15] "YER075C" "YER089C" "YER133W" "YFL029C" "YHR102W" "YHR135C" "YIL035C"
[22] "YIL113W" "YJL164C" "YJR066W" "YKL166C" "YKL203C" "YLR433C" "YML016C"
[29] "YML057W" "YMR216C" "YNL154C" "YNL307C" "YOL100W" "YOL128C" "YOR061W"
[36] "YOR208W" "YPL031C" "YPL203W"

Core layer:
[1] "YAR019C" "YBL105C" "YBR160W" "YDL017W" "YDR507C" "YFR028C" "YGR092W"
[8] "YHL007C" "YJL128C" "YJL187C" "YKL048C" "YKL101W" "YLR113W" "YLR362W"
[15] "YMR001C" "YMR036C" "YNL298W" "YNR031C" "YPL153C"

Bottom layer:
[1] "YBL016W" "YBR274W" "YDL028C" "YDL101C" "YDL108W" "YDL159W" "YDR283C"
[8] "YDR477W" "YER129W" "YFL033C" "YGL179C" "YGL180W" "YGR040W" "YGR188C"
[15] "YGR262C" "YHR030C" "YHR205W" "YJL095W" "YJL106W" "YJL141C" "YJR059W"
[22] "YKL126W" "YKL139W" "YLR096W" "YLR248W" "YMR104C" "YNL053W" "YNL161W"
[29] "YNL183C" "YNR047W" "YOR231W" "YOR233W" "YPL140C" "YPL209C" "YPR111W"
[36] "YPR161C"

Excluded actors:
[1] "YAL017W" "YBR059C" "YCR079W" "YDL230W" "YDR122W" "YER139C" "YGL059W"
[8] "YGR123C" "YHR004C" "YIL042C" "YIL095W" "YJL165C" "YKL161C" "YLL010C"
[15] "YLL019C" "YLR361C" "YMR139W" "YMR277W" "YNL020C" "YNL222W" "YOL045W"
[22] "YOR090C" "YOR351C" "YPL042C" "YPL204W" "YPR073C"

Disconnected actors:
[1] "YBR097W" "YBR098W" "YDR247W" "YER123W" "YFR014C" "YHR076W" "YKL171W"
[8] "YLR240W"

Disconnected targets:
[1] "YBR109C"   "YCR073W-A" "YDL215C"   "YDR080W"   "YOR125C"

Levels:
\$`Level: 9`
[1] "YMR216C"

\$`Level: 8-9`
[1] "YNL307C"

\$`Level: 8`
[1] "YML016C"

\$`Level: 7-9`
[1] "YBL088C"

\$`Level: 7-8`
[1] "YDR490C" "YJL164C"

\$`Level: 7`
[1] "YIL035C"

\$`Level: 6-9`
[1] "YBR125C" "YCR073C" "YDL006W" "YDL134C" "YDL188C" "YDR075W" "YER075C"
[8] "YFL029C" "YHR135C" "YLR433C" "YML057W" "YNL154C" "YOL100W" "YOR208W"

\$`Level: 6-8`
[1] "YBR136W"

\$`Level: 6-7`
[1] "YKL166C" "YOR061W" "YPL203W"

\$`Level: 6`
[1] "YBL056W" "YER089C"

\$`Level: 5`
[1] "YAR019C" "YBL105C" "YBR160W" "YDL017W" "YDR507C" "YFR028C" "YGR092W"
[8] "YHL007C" "YJL128C" "YJL187C" "YKL048C" "YKL101W" "YLR113W" "YLR362W"
[15] "YMR001C" "YMR036C" "YNL298W" "YNR031C" "YPL153C"

\$`Level: 4-9`
[1] "YDL047W" "YER133W"

\$`Level: 4`
[1] "YER129W"

\$`Level: 3-9`
[1] "YCR091W" "YJR066W" "YKL203C"

\$`Level: 3`
[1] "YDR477W" "YGL179C"

\$`Level: 2-9`
[1] "YDL079C" "YDR436W" "YHR102W" "YIL113W" "YOL128C" "YPL031C"

\$`Level: 2-4`
[1] "YDL028C" "YJL095W" "YKL126W" "YNR047W"

\$`Level: 2`
[1] "YHR205W"

\$`Level: 1-9`
[1] "YAL017W" "YBR059C" "YCR079W" "YDL230W" "YDR122W" "YER139C" "YGL059W"
[8] "YGR123C" "YHR004C" "YIL042C" "YIL095W" "YJL165C" "YKL161C" "YLL010C"
[15] "YLL019C" "YLR361C" "YMR139W" "YMR277W" "YNL020C" "YNL222W" "YOL045W"
[22] "YOR090C" "YOR351C" "YPL042C" "YPL204W" "YPR073C"

\$`Level: 1-8`
[1] "YDL108W" "YKL139W" "YNL161W" "YNL183C" "YPR161C"

\$`Level: 1-7`
[1] "YBR274W" "YMR104C"

\$`Level: 1-6`
[1] "YGL180W" "YJL141C"

\$`Level: 1-4`
[1] "YDL101C" "YJL106W" "YJR059W" "YLR096W" "YLR248W" "YOR233W" "YPL209C"
[8] "YPR111W"

\$`Level: 1-3`
[1] "YBL016W" "YDL159W" "YGR040W" "YGR188C" "YHR030C" "YNL053W" "YOR231W"
[8] "YPL140C"

\$`Level: 1-2`
[1] "YDR283C"

\$`Level: 1`
[1] "YFL033C" "YGR262C"

\$`Level: 0`
[1] "YAL003W" "YAL005C" "YAL019W" "YAL024C" "YAL028W" "YAL031C" "YAL038W"
[8] "YAL040C" "YAL041W" "YAL043C" "YAL047C" "YAR002W" "YAR007C" "YAR014C"
[15] "YBL002W" "YBL003C" "YBL007C" "YBL023C" "YBL032W" "YBL035C" "YBL039C"
[22] "YBL047C" "YBL051C" "YBL054W" "YBL063W" "YBL078C" "YBL084C" "YBL085W"
[29] "YBL097W" "YBL103C" "YBR009C" "YBR010W" "YBR021W" "YBR023C" "YBR028C"
[36] "YBR038W" "YBR060C" "YBR081C" "YBR083W" "YBR102C" "YBR112C" "YBR133C"
[43] "YBR135W" "YBR143C" "YBR156C" "YBR182C" "YBR200W" "YBR202W" "YBR247C"
[50] "YBR260C" "YCL011C" "YCL014W" "YCL024W" "YCL032W" "YCL037C" "YCL051W"
[57] "YCL061C" "YCL063W" "YCR002C" "YCR014C" "YCR053W" "YCR065W" "YCR077C"
[64] "YCR088W" "YDL003W" "YDL005C" "YDL022W" "YDL088C" "YDL089W" "YDL102W"
[71] "YDL106C" "YDL140C" "YDL149W" "YDL161W" "YDL195W" "YDL201W" "YDL220C"
[78] "YDL225W" "YDR001C" "YDR005C" "YDR028C" "YDR043C" "YDR052C" "YDR054C"
[85] "YDR076W" "YDR082W" "YDR097C" "YDR099W" "YDR103W" "YDR113C" "YDR118W"
[92] "YDR130C" "YDR138W" "YDR146C" "YDR162C" "YDR168W" "YDR169C" "YDR172W"
[99] "YDR184C" "YDR207C" "YDR216W" "YDR217C" "YDR223W" "YDR224C" "YDR225W"
[106] "YDR277C" "YDR285W" "YDR293C" "YDR301W" "YDR310C" "YDR325W" "YDR346C"
[113] "YDR348C" "YDR356W" "YDR369C" "YDR379W" "YDR385W" "YDR386W" "YDR388W"
[120] "YDR422C" "YDR432W" "YDR439W" "YDR443C" "YDR451C" "YDR463W" "YDR468C"
[127] "YDR480W" "YDR496C" "YDR499W" "YDR501W" "YEL009C" "YEL032W" "YEL061C"
[134] "YEL062W" "YER016W" "YER020W" "YER027C" "YER028C" "YER032W" "YER040W"
[141] "YER041W" "YER088C" "YER093C" "YER095W" "YER106W" "YER109C" "YER111C"
[148] "YER114C" "YER118C" "YER148W" "YER149C" "YER151C" "YER155C" "YER161C"
[155] "YER167W" "YER169W" "YER174C" "YER177W" "YER178W" "YFL014W" "YFL021W"
[162] "YFR015C" "YFR021W" "YFR027W" "YFR029W" "YFR034C" "YFR040W" "YFR046C"
[169] "YGL003C" "YGL008C" "YGL019W" "YGL035C" "YGL049C" "YGL058W" "YGL073W"
[176] "YGL075C" "YGL086W" "YGL090W" "YGL093W" "YGL113W" "YGL116W" "YGL122C"
[183] "YGL123W" "YGL163C" "YGL175C" "YGL201C" "YGL208W" "YGL253W" "YGR009C"
[190] "YGR035C" "YGR038W" "YGR082W" "YGR086C" "YGR097W" "YGR108W" "YGR113W"
[197] "YGR140W" "YGR184C" "YGR225W" "YGR233C" "YGR252W" "YGR270W" "YHL020C"
[204] "YHL027W" "YHR005C" "YHR014W" "YHR042W" "YHR071W" "YHR079C" "YHR082C"
[211] "YHR084W" "YHR098C" "YHR107C" "YHR118C" "YHR124W" "YHR149C" "YHR152W"
[218] "YHR154W" "YHR158C" "YHR159W" "YHR161C" "YHR164C" "YHR166C" "YHR172W"
[225] "YIL031W" "YIL033C" "YIL050W" "YIL066C" "YIL072W" "YIL101C" "YIL105C"
[232] "YIL106W" "YIL107C" "YIL109C" "YIL112W" "YIL122W" "YIL144W" "YIL149C"
[239] "YIL159W" "YIR006C" "YIR010W" "YIR023W" "YJL013C" "YJL026W" "YJL076W"
[246] "YJL084C" "YJL089W" "YJL092W" "YJL093C" "YJL098W" "YJL129C" "YJL157C"
[253] "YJL194W" "YJR007W" "YJR021C" "YJR033C" "YJR035W" "YJR049C" "YJR053W"
[260] "YJR057W" "YJR060W" "YJR072C" "YJR076C" "YJR083C" "YJR090C" "YJR092W"
[267] "YJR093C" "YJR094C" "YKL022C" "YKL035W" "YKL038W" "YKL042W" "YKL043W"
[274] "YKL052C" "YKL062W" "YKL089W" "YKL108W" "YKL112W" "YKL129C" "YKL159C"
[281] "YKL160W" "YKL178C" "YKL185W" "YKR002W" "YKR028W" "YKR037C" "YKR038C"
[288] "YKR048C" "YKR089C" "YKR090W" "YKR091W" "YKR095W" "YLL003W" "YLL021W"
[295] "YLL043W" "YLR006C" "YLR035C" "YLR045C" "YLR079W" "YLR086W" "YLR102C"
[302] "YLR103C" "YLR127C" "YLR131C" "YLR133W" "YLR138W" "YLR176C" "YLR182W"
[309] "YLR183C" "YLR187W" "YLR190W" "YLR206W" "YLR212C" "YLR219W" "YLR223C"
[316] "YLR258W" "YLR259C" "YLR263W" "YLR265C" "YLR272C" "YLR277C" "YLR288C"
[323] "YLR310C" "YLR314C" "YLR319C" "YLR335W" "YLR350W" "YLR371W" "YLR384C"
[330] "YLR399C" "YLR410W" "YLR425W" "YLR430W" "YLR437C" "YLR442C" "YLR452C"
[337] "YLR457C" "YML007W" "YML010W" "YML027W" "YML034W" "YML055W" "YML058W"
[344] "YML061C" "YML064C" "YML065W" "YML074C" "YML112W" "YML119W" "YMR005W"
[351] "YMR028W" "YMR032W" "YMR037C" "YMR055C" "YMR070W" "YMR109W" "YMR133W"
[358] "YMR153W" "YMR165C" "YMR172W" "YMR183C" "YMR186W" "YMR190C" "YMR205C"
[365] "YMR224C" "YMR232W" "YMR260C" "YMR273C" "YMR280C" "YMR309C" "YMR311C"
[372] "YNL004W" "YNL025C" "YNL027W" "YNL030W" "YNL031C" "YNL042W" "YNL047C"
[379] "YNL058C" "YNL068C" "YNL076W" "YNL088W" "YNL102W" "YNL118C" "YNL121C"
[386] "YNL126W" "YNL131W" "YNL152W" "YNL157W" "YNL167C" "YNL172W" "YNL178W"
[393] "YNL189W" "YNL197C" "YNL225C" "YNL233W" "YNL242W" "YNL243W" "YNL271C"
[400] "YNL272C" "YNL278W" "YNL289W" "YNL309W" "YNL312W" "YNL321W" "YNR009W"
[407] "YNR016C" "YNR052C" "YOL001W" "YOL018C" "YOL026C" "YOL054W" "YOL059W"
[414] "YOL070C" "YOL078W" "YOL083W" "YOL136C" "YOR014W" "YOR018W" "YOR026W"
[421] "YOR028C" "YOR032C" "YOR033C" "YOR047C" "YOR057W" "YOR058C" "YOR066W"
[428] "YOR070C" "YOR083W" "YOR098C" "YOR119C" "YOR127W" "YOR133W" "YOR140W"
[435] "YOR171C" "YOR174W" "YOR178C" "YOR181W" "YOR189W" "YOR195W" "YOR212W"
[442] "YOR217W" "YOR254C" "YOR257W" "YOR276W" "YOR315W" "YOR322C" "YOR324C"
[449] "YOR329C" "YOR347C" "YOR361C" "YOR372C" "YOR373W" "YPL004C" "YPL014W"
[456] "YPL049C" "YPL089C" "YPL115C" "YPL124W" "YPL133C" "YPL155C" "YPL232W"
[463] "YPL240C" "YPL248C" "YPL256C" "YPL267W" "YPL269W" "YPR007C" "YPR010C"
[470] "YPR016C" "YPR018W" "YPR019W" "YPR030W" "YPR040W" "YPR041W" "YPR054W"
[477] "YPR115W" "YPR119W" "YPR141C" "YPR171W" "YPR174C" "YPR175W" "YPR181C"
[484] "YPR185W"

Call:
summary.vertex.sort(object = vs_kp_net)

Graph description:
Nodes no  Edges no Layers no Levels no
616      1087         3         9

Layers description:
Top actors no   Core actors no Bottom actors no       Targets no
38               19               36              484

Excluded and disconnected nodes:
Excluded actors no  Disconnected actors no Disconnected targets no
26                       8                       5
[1] 9
```

VertexSort documentation built on May 2, 2019, 9:12 a.m.