SMA

Tree traversal, also known as tree search, is a process of visiting each node of a tree data structure. During tree traversal, you visit each node of a tree exactly once and perform an operation on the nodes like checking the node data (search) or updating the node.

Algorithms for doing tree traversal:

• Depth-First Search (DFS)
  • Branches are visited, one after the other
  • Three variations
• Breadth-First Search (BFS)
  • In layers, starting from the root 

A linear network is a linear sequence �� of connected vertices.

A ring network A is a network topology in which each node is connected to exactly two other nodes, forming a single continuous path, a ring. 

--> Biconnected: because we can delete a vertex or a node and the graph would still be connected

A star network is a tree �� with a single vertex of maximum degree.

Grid --> Optical fiber

Mesh --> IP Routing

• Initially studied by Erdős and Rényi in 1959:
  • Pairs of nodes are randomly connected by a given number of connections;
  • Two nodes are connected by a certain probability p.
• All nodes have approximately the same number of neighbors, which differs slightly from the average value.

• Unlike regular and random networks, complex networks capable of reproducing the properties of real interaction networks 
• Evolution of the classical graph theory into the modern theory of complex networks
• Non-intuitive characteristics and can be made up of millions of units communicating with each other
• Mathematical methods based on graph theory are therefore used to extract information from complex networks in a synthetic and objective way.
• Example: social networks

The first-order network is generally called the ego-centric network (or ego-network) --> focuses on the network surrounding a specific node

Networks that move away from the first order are called socio-centric networks --> concerns the study of "complete" networks

• Coined by Milgram who did experiment: sample of Americans were asked to deliver a message to a stranger of whom they only knew the name and a few other details but not the address only using network of acquaintances. Results: Average of only between 5 and 7 steps to reach the recipient.
• Short paths exist between individuals in large social networks. These paths can be found by ordinary people. 
• Examples of small world: WWW or e-mail exchange
• Edors number: How distant are you in regards to collaboration with mathematician Paul Erdos
• Bacon number: How distant are you in regards to collaboration with Kevin Bacon
• This property makes networks very efficient in terms of information propagation speed (e.g. infectious deseases)

• Tendency in social networks to create clusters --> communities of individuals all or almost all in relation to each other
• Already know previously as transitivity --> has been quantified by clustering coefficient (cc) -->  cc is larger in complex networks than correspondig random network.

• The strength of a tie is given by the combination of the amount of time, emotional intensity, intimacy  and the exchange of services that characterizes the tie.
• strong ties --> family, friends (primary network)
• weak ties --> informal networks of people, which, in terms of social integration and increase in social capital, are often more important than strong ties (e.g. when looking for a job)
• Tie strenght can be measured by different techniques:
  • Identifiying shortcut brdiges
  • Neighbourhood overlap assessment
  • Evaluation of user activities

A shortcdut bridge is a bridge, that once it is removed, it increases the distance between two nodes. 

Rare in social networks

The greater the distance, the "weaker" the type of tie.

You count how many edges you have to pass, if a bridge is removed. 

It measures how overlapping the neighbours are of two vertieces to measure strenght.

Calculation:

How many neighbours are shared between the two vertices divided by how many neighbours do the two vertices have in total (not counting double)

A Scale Free Network is one in which the distribution of links to nodes follows a power law. The power law means that the vast majority of nodes have very few connections, while a few important nodes (we call them Hubs) have a huge number of connections.

Hubs are basis of small-world effect -->  function of connecting areas of the graph that would otherwise be separate.