Application to Social Networks
Social and information networks are playing an important role in several applications. One of important problems here is classification of entities in the networks. In this chapter, we discuss several notions associated with social networks and the role o
- PDF / 210,072 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 210 Views
Application to Social Networks
Abstract Social and information networks are playing an important role in several applications. One of important problems here is classification of entities in the networks. In this chapter, we discuss several notions associated with social networks and the role of linear classifiers. Keywords Social network · Community detection · Link prediction · Learning Similarity function · Supervised learning
·
6.1 Introduction We discuss some of the issues related to representation of networks using graphs after introducing some basic terms.
6.1.1 What Is a Network? A network is a structure made up of a set of nodes and possible links between nodes. To simplify the discussion, we assume that there is at most one link between any pair of nodes. There are several applications where networks are commonly encountered and analyzed. Some of the well-known networks are internet and electrical network. For example, in the case of internet, a web page is a node in the network and a hyperlink from a web page to another web page is a link.
6.1.2 How Do We Represent It? Typically, such a network is represented by a simple graph. We illustrate it with the help of an example network shown in Fig. 6.1.
© The Author(s) 2016 M.N. Murty and R. Raghava, Support Vector Machines and Perceptrons, SpringerBriefs in Computer Science, DOI 10.1007/978-3-319-41063-0_6
69
70
6 Application to Social Networks
Fig. 6.1 Example network C
F
H
B
A
E
D
G
I
Some of the observations are: • There are nine nodes in the example network; they are labeled using A to I. • Between some pairs of nodes, there is a link; for example, node pairs A, B and G, I. • There is no link between some pairs of nodes; for example, node pairs A, E and H, I. • The graph shown in Fig. 6.1 is undirected. For example, the link between A and B may be represented either by A, B or B, A. Both are same. Such a representation conveys the notion of association between the two nodes. For example, A is a friend of B is the same as B is a friend of A. Such relations that are symmetric can be captured by undirected edges/links in the graph. • There are three simple paths between A and E. These are 1. Path A, B, E; here B is linked to both A and E. So, B is a common neighbor of A and E. 2. Path A, D, E; here D is linked to both A and E. So, D is a common neighbor of A and E. 3. Path A, C, F, E; here neither C nor F are linked to both A and E. So, neither C nor F is a common neighbor of A and E. 4. There is a notion of degree associated with each node. The degree of a node is the number of links associated with the node. The nodes in the example graph have the following degree profile: • Nodes of degree 2: the nodes labeled B, C, D, F, G, H, I are of degree 2. • Nodes of degree 3: observe that A has degree 3. • Nodes of degree 5: node E has degree 5. So, networks are represented using graphs. Further, graphs are popularly represented on the machine using two popular schemes. These are based on either adjacency matrix or adjacency list.
6.1 In
Data Loading...
