Free Online Courses for Software Developers - MrBool
× Please, log in to give us a feedback. Click here to login
×

You must be logged to download. Click here to login

×

MrBool is totally free and you can help us to help the Developers Community around the world

Yes, I'd like to help the MrBool and the Developers Community before download

No, I'd like to download without make the donation

×

MrBool is totally free and you can help us to help the Developers Community around the world

Yes, I'd like to help the MrBool and the Developers Community before download

No, I'd like to download without make the donation

Modeling Social Networks – Part 1

In the first part of this article we will see a simple network of relationships and a model that stores a generic social network.

This article discusses the modeling of a social network such as virtual networks behind social networking sites like Facebook and others. The main tables of the model are presented as a short review of graph theory. Both the model tables as operations on the data are presented from the point of view of a database, without worrying about implementation details in the present application that interacts with the data. In the first part of this article we will see a simple network of relationships and a model that stores a generic social network. In the second part will see the implementation of some algorithms for navigation in the social network.

Social Networks


One possible definition for social networks is based on the concept of virtual networks of relationships. This type of network aims to connect people who have some degree of affinity in addition to increase the interaction of each other. The link between users that the network provides can be represented by some kind of aspect that relates to people, for instance: common interests, familiarity, sharing some kind of hobby or even by simple chance. Finally, a social network helps people to be connected in some way and allow the exchange relationships between people in a broader sense.

Besides helping to link people, this type of network also provides access to specific forums on a particular subject. Many analysts believe that this type of forum, usually called community or group, is what really brings the dynamic and interactive aspect of a social networking web site. Thus users do not get bored easily with the network relationship and always have a reason to return to the site and check what is happening in the communities involved.

Perhaps the most common example is the social network site Facebook. After reaching levels of popularity never saw bore, this social network has achieved an impressive rate for this type of application. Initially, the entry on this type of social network needs an invitation from someone who was already registered. Recently, however, this invitation is no longer necessary and any internet user can join Facebook. Joining the basic features to promote interaction among the users with a friendly interface and easy to use, Facebook quickly became a phenomenon of use among worldwide users.

To begin connection yourself to other in Facebook you just need to register a profile through a series of questions that are not mandatory and go looking for relationships or communities to interact with others who already have a registered profile. Add to this network of relationships the ability to send messages, the possibility of publishing photos, texts and videos, some status information combined with a simple graphical interface to transform the application into a phenomenon never seen before in Internet.

Facebook was not the first social networking site in the internet, however. Perhaps the most prominent among the American public was MySpace which provided extra more features compared to Facebook, like adding features to blog posts in each profile. Although some differences are major, almost all Social Networking follow the basic principles of organization and relationship profiles.

Considering technical data requirement aspects this application does not have big complexity structures. In fact, the main asset is not in interface beauty or the amount of fancy features of the application, but the ease with which the network expands. In the end what matters is not the technology used in the application, but its ability to add users and keeping then making the application popular.

In this article we will discuss how to implement a simple social network from the point of view of the database. However, only some aspects of managing the relationships between users and a few navigation operations between them will be addressed. The dynamic part of this type of application, which involves the management of communities, messaging and other features, will not be discussed. The reader who has interest in the dynamic aspect of this application can easily find many ready-made solutions that are widely used and available on the Internet.

Some graph theory


To understand how the organization and management of users in a network of relationships, one must know some concepts of theory that can provide support for such a task. One common approach to this type of application is based on the graph theory.

Simply put, it can be said that a graph structure is based on a sets of two elements: a set of vertices and a set of edges. Normally we use the notation G (V, E) to identify a graph G which has a set of vertices V and a set of edges E.

It makes sense to think of graphs to represent a network of relationships. If we think that each profile can be represented by a vertex and the relationship between two profiles represented by an edge, it is easy to use all of the theoretical background that the graph theory provides. Thus, the entire structure of a network of relationships can be represented by the sets of vertices and edges. To avoid confusion this article uses the term profile in place of the vertex and the term relationship and to refer to an edge of a graph.

The graph theory has been studied for a long time. Thus we have the advantage of being able to count on a large set of references, algorithms, applications and views to our network of relationships. Let's see an example of a small network of relationships that will be used throughout the article.

Suppose we have six profiles on our network of relationship: Mauro, Leda, Erika, Maike, Edilson and Aline. Thus the set V would be as follows: V = {Aline, Erika, Leda, Mauro, Maike, Edilson}. Now assume that these profiles are related as follows:

Mauro is friend of all profiles.
Leda is only friend of the profiles Mauro, Erika,  Maike, and Edilson.
Erika is only friend of the profiles Mauro, Leda, and Aline.
Maike is friend of profiles Mauro, Leda, and Edilson.
Edilson is friend of the profiles Mauro, Leda. and Maike.
Aline is friend of Mauro and Erika.


The set E, containing the relationships of the profiles of set V, store pairs of relationships between two persons without worrying about the order. Then E = {(Mauro, Leda), (Mauro, Erika), (Mauro, Maike), (Mauro, Edilson), (Mauro, Aline), (Leda, Erika), (Leda, Maike), (Leda, Edilson ), (Erika Aline), (Maike, Edilson)}. Because the relationship of friendship is bidirectional, i.e. if person A is a friend of a person B then B is a friend of A, we can represent the relationship as a pair-wise relation between A and B in a inside the set E.

There are several computer data structures used to store graph data. The most common are matrices and adjacency lists. There is also the approach that follows the principles of object orientation, where modeling the graph storage makes use of classes related by composition. In short, these are the main ways of storing graph data in a computer. It is important to note that the data structure called trees, whether binary red-black or any other type, are considered special graphs and also can be stored using the same data structures that the graphs.

The various operations performed on graphs do not directly depend on the manner in which the graph was implemented. This is due to the fact that these operations are generally described at high level, without taking into account the atomic operations, such as visiting a vertex or an edge to remove it. Thus the description of the operation is separated from the implementation, allowing a high degree of abstraction in the handling of the elements of the graph. For example, the use of binary trees, which are represented by a graph containing numeric values at each vertex, the algorithm can be described to include a new node (vertex) as follows:

If the tree is empty, then add a new node at this point. Otherwise, do the following:
a) If the new data is smaller than the given root, include it in the left sub-tree.
b) If the new data is larger than the given root, include it in the right sub-tree.

Note that the algorithm described above only abstract operations (such as inserting a node) are presented without the need to describe step by step how this operation will be effectively implemented.

From the data of the example graph we can set up multiple views of the relationships. Figure 1 shows the graph data formatted as a mind map. Figure 2 shows the data in the form of a hyperbolic tree. Figure 3 presents the data as a two-dimensional graph. Figure 4 presents the data in the form of a three-dimensional graph. Figure 5 shows the data as a conceptual map. Finally, Figure 6 shows the image list that connects the profiles.

Each representation of the graph has a specific function and allows the user to interact with the graph by changing the position of the vertices to better visualize the network. The mind maps are more useful for the separation of relationships around a central idea. The hyperbolic trees represent the form of a circular tree in the sense of viewing the information around a vertex that is always in the center.

The two-dimensional view of a graph is the most traditional and emphasizes the notion of connection between vertices. On the other side, the three-dimensional representation of the graph allows us to highlight the focus of the vertices by placing them in the foreground compared to each other. Finally, the use of concept maps allows the specification of semantic relationships of some characteristic, such as the degree of friendship between network profiles.

The list of images faithfully represents the use of an adjacency list, where each profile is a list that represents the relationship between the other profiles.


Figure 1. Visualization of the relationship graph – Mind Map.


Figure 2. Visualization of the relationship graph – Hyperbolical tree.


Figure 3. Visualization of the relationship graph – bidimensional graph.


Figure 4. Visualization of the relationship graph – tridimensional graph.


Figure 5. Visualization of the relationship graph – Conceptual map.


Figure 6. Visualization of the relationship graph - List of images.

Modeling the entities


From the point of view of databases we can think of a diagram containing the entities that represent the static aspect of a social network, i.e. the profiles and relationships between them. Figure 7 shows a diagram of entities that models the static aspect of a simple social network.


Figure 7. Simple model of a social network.

For teaching purposes the model of Figure 7 shows only some information in order to illustrate the operations that can be made with the network’s relationships. According to this model, users must be registered in the table PROFILE and the personal details must be are stored in the DETAILS table. We establish a 1-1 relationship between these tables 1-1 through ID_DETAIL column placed in both tables. This model gives only some information from the user profile, but social networks require from the user more personal information to better identify their profile. Table 1 shows the lines of the example graph stored in the table without the column ID_DETAIL in order to simplify the presentation of data. Note that the column NICKNAME_PROFILE was placed next the value of the number of friends to the name of the profile, and that column QTY_TOTAL all profiles have the value 5 since they are all related to the profile Mauro that is everyone's friend.


Table 1. Example graph data stored in the PROFILE table.

The relationship between user profiles is modeled by FRIENDS table which relates to the PROFILE table by the columns ID_PROFILE_A and ID_PROFILE_B. Using a separate table to store the relationship of friendship is necessary due to information on the degree of friendship that a profile can have over another (friend, acquaintance, fan, etc.) which is specified in column DEGREE_FRIENDSHIP. The columns GROUP and TRUSTWORTHY all the definition of friends based on relationships (friends from school, work) and specifying the level of reliability of this relationship (very reliable, unreliable),  respectively. Just as other details can be specified to make a profile richer, more information can be added to the model to provide more details about how the relationships between the status relationships (friends forever, 'bad', 'good' ) and personal information.

This simplistic the model has a mechanism to distinguish relationships. For example, if user A is friend of user B that means the user B is also a friend of user A, but as it is possible to varying degrees in every relationship, you need two rows in the table FRIENDS to represent these relationships a friendship between A with B and between B with A.

In most social networks the friendship relation requires that an existing profile make an invitation to another profile and the profile that is receiving the invitation to approve the creation of this relationship. These tasks do not always happen immediately, since the approval may take some time. In these cases the model behaves as follows: at the time of the request a row is inserted in the FRIENDS table indicating the relationship between the profile that made the request in the ID_PROFILE_A and the profile receive the invitation is stored in the ID_PERFIL_B column, leaving the column value OK false to indicate that there has been no approval of this call. When the user who received the invitation has approved, a new row is inserted into the table, but this time he received his invitation is stored in the column ID_PERFIL_A, who made the call is stored in column ID_PROFILE_B. If the profile that received the invitation does not approve of the relationship, the line was inserted into the table with friends is removed. Thus, the model involves the insertion of two rows in the table for each direction of the relationship. This model is similar to the call list data structure used to store the adjacency graph. This way you can make the most of the algorithms for manipulating graphs written based on this structure. To facilitate the understanding of relationships, Table 2 shows the relationships of the Mauro (dark gray) and Leda profile (light gray).


Table 2. Relationships of the Leda and Mauro profiles stored in the table FRIENDS.

Another important feature of this model is the denormalization of some information. The column QTY_FRIENDS in the PROFILE table aims to store all the friends of a certain profile. Obviously, this information can be obtained with a simple instruction count on the FRIENDS table, but for performance reasons one must avoids the instruction execution count storing the amount of friends in the profile QTY_FRIENDS column, and the amount of all friends can be reachable from a specific column profile.

The Denormalization presented by the columns QTY_FRIENDS and QTY_TOTAL implies an extra effort for consistency. Thus, whenever there is a change in the PROFILE or FRIENDS table is necessary to perform calculations to update the values of the columns QTY_FRIENDS and QTY_TOTAL. This type of calculation is often implemented in relational databases using constraints, triggers, or jobs, depending on the urgency and the availability of this information.

One last note on the model of Figure 2: only the static relationships of a social network have been implemented. The model can be extended from the insertion of new tables and columns to add the dynamic aspects, such as the use of communities, message exchanges between profiles and other features.

Conclusion


In the first part of this article about F we could understand the concept of a social network and its operations regarding the relationship between users. Next, we review graph theory presented with the objective to support the concepts used in navigation algorithms that will be addressed in the second part of this article. Following the model of social network was presented and its main characteristics were discussed.

References


Download FreeMind tool, which draws mind maps:
http://freemind.sourceforge.net/wiki/index.php/Main_Page
Download the tool Xebece, which draws Hyperbolic trees:
http://xebece.sourceforge.net/
Download the toolkit Ucinet, which draws two-dimensional and three-dimensional graphs:
http://www.analytictech.com/downloaduc6.htm
Download the tool CMap Tools, which draw concept maps:
http://cmap.ihmc.us


 



Mauro Pichiliani has the Master of Science degree on collaborative systems by the Aeronatics Institute of Technology (ITA) in Brazil. He is a specialist on database technologies with more than 8 years of experience on the industry...

What did you think of this post?
Services
[Close]
To have full access to this post (or download the associated files) you must have MrBool Credits.

  See the prices for this post in Mr.Bool Credits System below:

Individually – in this case the price for this post is US$ 0,00 (Buy it now)
in this case you will buy only this video by paying the full price with no discount.

Package of 10 credits - in this case the price for this post is US$ 0,00
This subscription is ideal if you want to download few videos. In this plan you will receive a discount of 50% in each video. Subscribe for this package!

Package of 50 credits – in this case the price for this post is US$ 0,00
This subscription is ideal if you want to download several videos. In this plan you will receive a discount of 83% in each video. Subscribe for this package!


> More info about MrBool Credits
[Close]
You must be logged to download.

Click here to login