The earliest social network?

I am currently reading a book called Linked by Albert-Laszlo Barabasi. It is a fascinating look at an area in which I have an intense interest - the development of networks. One of the anecdotes Barabasi uses is his pointing arguably one of the earliest social networks:

Early Christians were a renegade Jewish sect that were persecuted by both Jewish and Roman authorities with a reach that should have by all intents and purposes been bound to the scope of Judaism. In a time where news and ideas traveled by foot, distances were long and society was very fragmented, Christianity would it seem doomed to oblivion. So how despite all the odds do approximately 2 billion people call themselves Christians today?

Many credit the rise of Christianity due to the message offered by Jesus of Nazareth - his message was "sticky" - resonating and passing down the generations whilst other religions faded away. However, it has been pointed out that the success of Christianity arguably could be credited to an orthodox and pious Jew who never met Jesus. His Hebrew name was Saul, but was more commonly known to us by his Roman name, Paul. Paul's life was to curb Christianity. He traveled from community to community persecuting Christians because they put Jesus condemned as a blasphemer on the same level as God. He used every means at his disposal to uphold the traditions and force these people to adhere to Jewish law. However, historical records have shown that Paul went through a sudden conversion in the year 34 and became a fierce supporter of the new faith, making it possible for a small Jewish sect to become the dominant religion in the Western world.

Paul's success was due to his understanding that the message had to spread, so using his firsthand knowledge of the social network of the first century's civilised world from Rome to Jerusalem, he set out to reach and convert as many people as he could. He walked nearly 10,000 miles in the next 12 years of his life. However, he did not walk randomly, he reached out to places which held the biggest communities of his era, to the places where faith could germinate and spread more effectively. He was the first and by far the most effective salesperson of Christianity, using theology and social networks equally effectively. In effect he was a bridge builder between Christian communities and a master of first century social and religious links - the only network at the beginning of the modern era that could carry and spread a faith.

One could start to ask if this was a small world network.