Lab questions Flashcards
What is an adjacency matrix?
A of a graph is a square matrix with rows and columns equal to the number of vertices in the graph. The presence of an edge between vertices is repredented with a 1 otherwise it’s 0. For undirected graphs, the adjacency matrix is symmetrical.
What are some attributes a graph can have?
It can be weighted, directed, named etc
What are some examples of different types of graphs? Like in the way they look with node placement etc
Full graph (completely connected), # Star graph (directed towards a central node), # Tree graph (undirected, multiple “branches”), # Ring graph (unidirected, connects all vertices in a circular pattern)
What happens if you combine two graphs?
Combining two graphs does not merge their vertices by default (disjoint union), it only displays them in the same plot.
What is network density?
Network density describes the portion of the potential connections in a network that are real connections. A “potential connection” is a connection that could potentially exist between two vertices, regardless of whether or not it actually does.
What is network transivity?
Network transitivity is the probability for the network to have adjacent nodes interconnected, which reveals the existence of tightly connected communities (or clusters, subgroups, cliques…).
It is calculated as the ratio between the observed number of closed triplets and the sum of closed and open triplets in the graph.
Global transitivity (for an entire graph) is also referred to as global clustering coefficient.
So it’s closed triplets/closed+open triplets
What is netwrok diameter?
Network diameter is defined as the maximum shortest path between any two nodes in the network.
What is centrality?
Thus, the definition of centrality is not general and depends on the application.
Since there is no consensus about the definition of centrality, several measures have been proposed, where each one considers specific concepts. In this Lab, we will cover the following centrality measures:
Degree
Closeness
Eigenvector
Betweenness
What is degree centrality?
The simplest centrality measure is the degree centrality, which is defined by the number of connections attached to each node.
In-degree represents the number of directed connections reaching a node, while out-degree represents the number of directed edges leaving a node.
What is clsoeness centrality?
Node centrality can also be defined in terms of the shortest paths. A central node, therefore, should be close to all other nodes in the network in terms of their shortest path distances.
This idea is enclosed in the closeness centrality measure, which is defined in terms of the average distance of each node to all others.
What is Eigenvectors centrality
We can also define centrality in terms of the neighborhood of each node. We can assume that a node is important if it is linked to other important nodes.
The “importance” of a node is defined by the first eigenvector of the graph adjacency matrix, associated with the eigenvalue. Thus, this centrality is called eigenvector centrality.
Eigenvectors are a special set of vectors associated with a linear system of equations, such as a matrix equation. The direction of an eigenvector remains unchanged when a linear transformation is applied to it. They are also known as characteristic vectors, proper vectors, or latent vectors.
What is betweeness centrality?
Finally, if we measure the centrality as the number of shortest paths going through a vertex or an edge, we would be ranking them based on their betweenness centrality.
Describe hubs and authorties in a biological context
Hubs were expected to contain pages with a large number of outgoing links, while authorities would get many incoming links from hubs, presumably because of their high-quality relevant information.
In the biological context, the protein–protein interaction (PPI) network has a small number of highly-connected proteins (hubs) surrounded by a majority of lowly-connected proteins.
The malfunction of a hub is more likely to be lethal to an organism than the perturbation of a lowly connected node because hubs are more important than non-hubs in organizing the global network structure. This phenomenon is known as the centrality-lethality rule.
What are party and date hubs?
Protein hubs can be classified into two classes:
Party hubs, which coordinate a specific cellular process or protein complex, at a certain time.
Date hubs, which link together and convey information between different function‐specific modules or complexes, at different times.
What is average path lenght?
Average path length: mean of shortest distance between each pair of nodes, # (in both directions for directed graphs). One can when making a graph choose colors depenidng on the path lenght to visualize the path lenght easier