Networks: Theory and Applications


SI508 home


software tools

related courses


Lada Adamic

Useful links:



Pajek download page

Pajek datafiles for this class

A planar graph and layouts in Pajek
Download the file '' from the ctools website.

  • Open it in Pajek by either clicking on the yellow folder icon under the word "Network" or by selecting File>Network>Read from the main menu panel
    A report window should pop up confirming that the graph has been read and the filename and location will be displayed in the 'active' position of the network dropdown list.
  • Visualize the network using Pajek's Draw>Draw command from the main menu panel.
    This will bring up the 'draw' window with its own menu bar at the top
  • Reposition the vertices by clicking on them and holding down the mouse button while dragging them to a new location. Continue doing this until you have shown that the graph is planar (no edges cross have to cross )
    (If you think this is really fun to do in your spare time, go to
  • Now let Pajek do the work for you by selecting from the draw toolbar several layout algorithms under 'Layout>Energy'.
  • Why did you select the layout algorithm you did?
  • Did the layout leave any lines crossed? If you were to do this assignment over, what order would you do it in?


dining table partners:

1 Strongly connected components and bowtie structure
Download the file This data set is provided with the book 'Exploratory Social Network Analysis with Pajek'. It represents the first and second choices in dining table partners by the residents of a girls' school dormitory. Suppose each of the girls has a secret. A girl will share her secret only with her 1st or 2nd choice of dining partner. But once she has shared her info, her 1st and 2nd choice partners will not be able to resist sharing her secret with their 1st or 2nd choice, etc.

  • Find groups of girls who will all know each other's secrets (hint: try Net>Components>Strong and Draw>Draw-partition)
  • Which girls will get to know no secrets but their own?
  • Display the network of strongly connected components (Operations>Shrink Network>Partition and Draw>Draw-partition)
  • Go back to the original (not-shrunk) network. Identify the bowtie structure (Net>Partitions>Bow-Tie).
  • What part of the bowtie is missing? What does this imply for the circulation of gossip?

2 Snowball Sampling
Keep working with the same network of girls. You are a prince who just met an enchanting young lady at a ball, but she left at the stroke of midnight and left a shoe behind. Now you'd like to find the shoe's owner. All you know about her is that she lives in this particular girls' dorm. The headmistress won't let you talk to the girls, so the only way you can find your princess is to covertly ask the one girl you know, Ella, to introduce you to her two favorite friends. Once you know her friends, you can ask them to introduce you to their two favorite friends, etc. This is a snowball sampling technique.

Highlight the vertices that you will reach using snowball sampling (Net > K-Neighbors > ...) .
Which girls will you not find using snowball sampling starting with Ella?

actors & movies:
Download the file

  • Open it in Pajek.
  • This is a 2 mode network containing two classes of nodes, actors and movies. Create a 2-mode partition (Net>Partition>2-Mode). Now draw the network (Draw>Draw-Partition). The two classes of nodes should be colored differently. If labels are not shown, add them (Options>Mark Vertices Using>Labels). Apply your favorite layout algorithm.
  • Transfrom the network into a one-mode network (Net>Transform>2-Mode to 1-Mode>Rows). Draw the network (Draw>Draw). Qualitatively compare the structure of the 2-Mode to the 1-Mode network. Is there a loss of information?
  • Show the weights on each edge using (Options>Lines>Mark Lines>with Values). What do the values represent?
  • Compute the unweighted degree of each node (Net>Partitions>Degree>All). Next draw the network using (Draw>Draw-vector). How is the degree represented? Add the vector value to each vertex (it will be the degree/(max possible degree)) (Options>Mark Vertices Using>Vector Values). Who are the most important actors using this measure?
  • Remove all edges between actors who have costarred in fewer than 3 movies (Net>Transform>Remove>Lines with value>Lower than). Which actors comprise the central core of this network?

models of networks:

Small world structure demo

Random network (Erdos-Renyi) demo

Preferential attachment demo

community structure, search and robustness - link to online demos

information diffusion demos

1. Diffusion in a random graph


How does varying the density (average degree) of the network influence the speed of diffusion? Explain in terms of the network structure.

Also vary the probability that an infected node infects a particular neighbor at each time step. How does this influence the overall infection rate (measured as the cumulative number of infected individuals).

Submit a screenshot or two (*I*).

2. Diffusion in a small world


Start by setting the rewiring probability to 0. Observe the speed of diffusion in terms of the cumulative number of individuals infected.

Increase the rewiring probability just a bit, so you have only a few shortcut edges. How is the rate of diffusion affected?

Now increase the rewiring probability further. How much more of a difference does this have on the speed with which the disease is spreading.

3. Diffusion in a network resulting from a growth process


How does varying gamma (which influences whether the growth is preferential or not) influence the speed of diffusion?