Can a graph exhibit both Preferential Attachment and Small-World properties at the same time?

274 Views Asked by At

I am analyzing a graph of protein-protein interactions. The data has been sourced from the STRING website.

The original directed multigraph has been converted as follows: select largest strongly connected component subgraph, then convert to an undirected graph.

Number of nodes: 3756
Number of edges: 56584
Average degree:  30.1299

During further analysis I observe that:

  • The graph appears to exhibit the properties of a small-world graph, namely the graph's average shortest path is small (3.12) and its clustering coefficient is relatively high (0.46). This, I believe, is also referred to as the Preferential Attachment Model.

  • The graph's degree distribution exhibits small world properties i.e. most nodes have small degree and some nodes have very high degree.

enter image description here

Now, I am not a great expert in graph theory and mathematics, but I am curious to find out if the above findings are in any way contradictory, indicating a problem with the underlying graph, or whether this is indeed something that can be observed in real-world networks.