Modeling an web community discovery method with web page attraction

Abstract

An improved Web community discovery algorithm is proposed in this paper based on the attraction between Web pages to effectively reduce the complexity of Web community discovery. The proposed algorithm treats each Web page in the Web pages collection as an individual with attraction based on the theory of universal gravitation, elaborates the discovery and evolution process of Web community from a Web page in the Web pages collection, defines the priority rules of Web community size and Web page similarity, and gives the calculation formula of the change in Web page similarity. Finally, an experimental platform is built to analyze the specific discovery process of the Web community in detail, and the changes in cumulative distribution of Web page similarity are discussed. The results show that the change in the similarity of a new page satisfies the power-law distribution, and the similarity of a new page is proportional to the size of Web community that the new page chooses to join.

Keywords

Web community web page attraction evolution process web page similarity

1 Introduction

Web community is a unique group composed of units and individuals who share common topics or interests. It is manifested by the fact that they communicate with each other through a mutually agreed Web page under a certain content. Many researches are devoted to community discovery technologies [1 –4] which are basically based on Web hyperlink analysis, apply the influence of Web structure on the community to discover the characteristics of the community and basically treat the Web as a huge graph.

In the current study, the definition of community characteristics is roughly divided into three categories [5 –10]: first, the characteristics of link structure of the community are discovered by the hub and authority collections in the HITS algorithm defined by Gibson et al. [11]. The greater the degree of ordered structure extracted by HITS is, the greater the number of community-related pages and the density of hyperlinks. ARC and CLEVER implemented a complete Web community discovery system on the basis of pure HITS algorithm, and Toyoda and Kitsregawa proposed the Companion algorithm that considers the order of links on the page and improved the pure HITS algorithm; second, Flake et al. [12] proposed a method to discover the Web community from another perspective according to the graph theory, and treated the community as a collection of closely connected pages, that is, the number of links between nodes inside the community is greater than the number of links outside the community; the third category is the trawling algorithm proposed by Kumar et al. [13] and the loose reference proposed by Reddy et al. [14], which are based on the bipartite directed graph technology. The proposed method abstracts the community into a bipartite directed graph. A dense bipartite graph may contain at least one community. Unlike HITS, the source of data is not based on a specific topic, but on general crawling results.

Researchers have proposed a number of analytical methods. Justine et al. [15] proposed an algorithm to approximate Web communities from the topic related Web pages, and varied the approximation values to identify varied degrees of relationship between Web pages. Murata et al. [16] proposed a method for visualizing Web communities and their internal structures, and succeeded in clarifying various genres of Web communities. Paola et al. [17] proposed a semiautomated strategy to extract domain-specific taxonomies from Web documents and its application to model a network of excellence in the emerging research field of enterprise interoperability. Georgios et al. [18] explained how to draw together the different viewpoints on Web communities and introduced new opportunities for community-based personalization, and proposed the concept of active user community and showed how this related to recent efforts on mining networks. Tzekina et al. [19] proposed a novel content-ignorant Web community feature space which was created by exploiting link analysis, and experimental results showed that the proposed Web community feature space generated much better results than the URL feature space. Han et al. [20] proposed a Fact-based Quality Assessment approach, which captured the data quality based on content semantics by gleaning the Web community knowledge, and FQA could automatically rank the Web data quality in terms of the accuracy of three most important quality dimensions.

Most of the existing community discovery methods focus on static community discovery, which cannot effectively analyze the network evolution, and the entity data of the community is often interchangeable and temporal, so the dynamic community discovery algorithm has attracted extensive attention from researchers [21]. Cazabet et al. [22] proposed the iLCD algorithm to update and merge the communities of the previous snapshot network according to the changes of network topology, and generated a new community to discover the community structure of the current snapshot network. The proposed algorithm can discover the overlapping communities in dynamic networks. Agarwal et al. [23] integrated the node-level behavior evolution into the algorithm, which can be divided into node addition, node deletion, edge addition and edge deletion, and their corresponding methods. Cordeiro et al. [24] focused on the community where nodes and edges were added or deleted, and redivided the community only for the changed elements based on the idea of local modularity maximization, without operating on other elements, thus greatly improving the operating efficiency. Duan et al. [25] designed an incremental k-agglomeration cluster algorithm for community discovery in dynamic networks. Variable flow model was used, and the Cluster Percolation Method (CPM) was improved by the depth-first search. Dynamic community discovery is performed from the perspective of node-level behavior evolution. The running speed of the proposed algorithm on DBLP and Enron datasets is much faster than that of the corresponding static algorithm. Xin et al. [26] proposed the Adaptive Random Walk Sampling (ARWS) algorithm for dynamic community discovery. ARWS algorithm solves the instability problem caused by fixed random walk, and realizes the non-uniform random walk of the object. Moreover, ARWS algorithm enables the affected nodes to find new neighbors and changing communities adaptively. Sattari et al. [27] proposed a new dynamic network evolution clustering method based on label propagation algorithm. The community label of each node is determined by its neighbors, and the node label is updated in a special order related to the network structure, and an attribution factor is assigned to each label. One of the node labels is considered as the primary community, and the other labels are considered as part of the secondary community. By iteratively updating node labels, each node can retain one or more community labels, so as to detect non-overlapping and overlapping communities in dynamic networks. He et al. [28] proposed a fast algorithm for dynamic community detection in time network, which makes use of the historical community information in the previous time sequence, constructs a small network through the historical community structure, and detects the communities in new network using the Louvain [29] algorithm.

However, the traditional methods still have the following shortcomings: (1) They all require an equidistant diffusion search from a Web page, so the accuracy of these algorithms depends largely on the location of the selected start page in the Web community. The resulting Web community is valid only when the Web page is located at the center of the Web community; (2) They have high time complexity, generally O (n²), in which n is the number of Web pages in the Web pages collection; (3) They are unable to detect the changing trend of the Web community, which makes it impossible for us to know in real time how people’s concerns about society are reflected on the Internet. As a result, the time complexity of Web community discovery is reduced by the attraction between Web pages. We explained the basic evolution process of the Web community by introducing the WSP and PDP rules, and verified our points of view according to the actual situation of the Web.

2 Improved web community discovery algorithm

Universal gravitation is an interaction between objects due to their mass, and its magnitude depends on the mass of the object and the distance between two objects. The greater the mass of the object is, the greater the universal gravitation between them, and the farther the distance between objects, the smaller the universal gravitation between them.

Definition 1 (attraction between Web pages): We treat each Web page in the Web pages collection as an individual with attraction according to the theory of universal gravitation. They constantly attract the surrounding Web pages to become a member of their own Web community. The attraction G between Web pages is defined as: $G_{i, j} = α \frac{k_{i} k_{j}}{r^{2}} + γ \frac{n_{i}}{Δ T}$ (1)

Where, G_i,j is the attraction of Web page i to Web page j, k_i and k_j are the node degree of Web page i to Web page j respectively, ΔT = t - t_i, t_i represents that Web page i joins the network at t_i, n_i is the number of connections obtained by Web page i within ΔT, α and γ are adjusting parameters which satisfy α + γ = 1.

The attraction of a Web page in the Web pages collection is related to the degree of the Web page and the evolution of the Web community. The greater the similarity of a Web page is, the greater the attraction. If the similarity of a Web page is larger than that of all its neighbors, it will easily attract the surrounding Web pages to its own Web community. However, if the similarity of a Web page is smaller than that of all its neighbors, it will be easily attracted by the surrounding Web pages, and it tends to be attracted by the largest one in its neighbors to become a member of the Web community where such Web page is located. Degree represents the topological position of a Web page in the network, and is a static measure at a certain moment. The attraction between Web pages describes how the structure of a Web community changes over a period of time and is a measure of dynamic process.

Therefore, both static network structure and dynamic network structure changing with time can apply the proposed algorithm for Web community discovery. The algorithm process of finding the Web community where a Web page in the Web pages collection is located is as follows:

The Web pages collection is read in. Each web page is recorded as a linked list structure in the following format (see Table 1). The time complexity of completing the linked list in the Web pages collection is O (E), where E is the number of hyperlinks in the Web pages collection.

If a Web page is pa and its neighbor is npa, then it exists. If the attraction value of pa is greater than that of npa and the attraction value of pa is greater than that of npa’s other neighbors, then pa is npa’s Web page with the maximum attraction. So npa is attracted by pa and becomes a member of the Web community where pa is located; if the attraction value of pa is less than that of npa and the attraction value of pa’s other neighbor nodes is less than that of npa, then npa is pa’s Web page with the maximum attraction. So pa is attracted by npa and becomes a member of the Web community where npa is located; if neither of the above two conditions can be met, then pa and npa are considered to be unable to attract each other, and they belong to two different Web communities, and they are the demarcation points of these two Web communities.

We take the Web page attracted by pa or npa as the new start page, and repeat step (2) until the demarcation point is discovered. Then, we find the structure of the whole Web community where a Web page is located. The time complexity is O(E).

Table 1

Linked List Structure of Web Page

Web Page	Attraction	No. of the Neighbor Web	Attraction Value of the Neighbor	List of Neighbor Web
No.	Value	Page with the Maximum Attraction	Web Page with the Maximum Attraction	Pages

To get the Web community of the whole Web pages collection, we need to start from any Web page to find the Web community where it is located according to the above three steps, and then start from any Web page outside the Web community to find another Web community according to the above three steps until all the Web pages are divided into corresponding Web communities. Each Web page will be searched once in the whole search process. For the Web pages collection with E hyperlinks, the time complexity of the whole algorithm is O(E). The proposed algorithm has a considerable improvement in performance compared with the time complexity O(n²) of traditional algorithm, and we do not need to specify the Web page of authority center when selecting the start page (see Table 2).

Table 2

The Structure of Algorithm

Algorithm: Attraction-based Web community discovery algorithm
Input: Web pages collection linked list L
Output: Community structure C
1. C←0
2. for pa∈V and npa∈A_pa do
3. if G_pa > G_npa and G_pa > max(G(A_npa))
4. C_pa←npa
5. else if G_pa < G_npa and G_npa > max(G(A_pa))
6. C_npa←pa
7. return C

3 Web community evolution model

3.1 Evolution process of Web community

According to the daily average user attention data provided by Baidu, we selected several representative websites for data analysis, as shown in Table 3. From the listed data, we can see that the daily average user attention of Internet-based websites is much higher than that of non-Internet-based websites. In other words, a website with more pages and more types of pages will attract more users to visit. When users are interested in a topic, they often first choose the website to obtain information or first cite the URL of such website to reprint the topic. Therefore, for the Web community, the larger the Web community is, the more pages in the community focus on the same topic (which indicates that the topic is hot). Users have more opportunities to get access to such topics, and they often link this topic to their own Web pages out of curiosity. With the gradual expansion of the scope, the Web community is expanding rapidly.

Table 3
Daily Average User Attentions of Different Websites From April to September 2007

Time Netease Sina Microsoft IBM Lenovo People’s Bank of China Sichuan University University of Electronic Science and Technology of China

2007.9 44229 104411 1991 3588 9475 809 1779 877

2007.8 42751 101637 2113 3354 9172 706 1820 890

2007.7 43220 106818 2046 3416 9408 712 2369 939

2007.6 38519 85585 1890 2663 9798 448 1613 871

2007.5 35999 109152 2197 3519 9726 412 1910 920

2007.4 36175 110328 1965 2610 7626 841 1994 930

Time	Netease	Sina	Microsoft	IBM	Lenovo	People’s Bank of China	Sichuan University	University of Electronic Science and Technology of China
2007.9	44229	104411	1991	3588	9475	809	1779	877
2007.8	42751	101637	2113	3354	9172	706	1820	890
2007.7	43220	106818	2046	3416	9408	712	2369	939
2007.6	38519	85585	1890	2663	9798	448	1613	871
2007.5	35999	109152	2197	3519	9726	412	1910	920
2007.4	36175	110328	1965	2610	7626	841	1994	930

Assuming that there are m Web communities in the initial Web, and each Web community consists of n₁, n₂,... n_m Web pages linked by hyperlinks, and these m Web communities are also linked by hyperlinks. The Web pages used to contact these Web communities are randomly selected. During the evolution of the Web community, a new Web community is added to the Web with probability pro every time, and the new Web community contains n_n Web pages linked by hyperlinks. A Web page is randomly selected from the new Web community and contacts with other Web communities through k hyperlinks. A new page is added to the Web with probability 1-pro. The Web page joins a Web community in the Web according to the WSP rule, and connects with other Web pages in the community with probability pro^′ through K hyperlinks, and with other Web communities outside the community with probability 1- pro^′. Among them, 0 ⩽ pro ⩽ 1, 0 ⩽ pro′ ⩽ 1. When pro = 0, there are no new Web communities formed in the Web. However, when pro = 1, a new Web community is formed in the Web. When a Web page selects the Web page in other Web communities as its neighbor, another Web community is first selected according to the WSP rule. According to our definition in the first section, the greater the similarity of a Web page is, the greater its attraction to other Web pages. Then, when a Web page joins a large Web community, it will select a Web page with greater similarity in the community to contact according to the PSP rule. These two priority rules are defined as follows:

Definition 2 (priority rule of Web community size WSP). When a Web page joins a Web community, the probability P (w_a) that the web page selects a Web community a is proportional to the size w_a of the Web community. We call this the WSP rule, which is expressed as: $P (w_{a}) = \frac{w_{a}}{\sum_{i = 1}^{m} w_{i}}$ (2)

Definition 3 (priority rule of Web page similarity PDP). When a Web page selects a page from the Web community a (which can be the Web community where the Web page is now located, or other Web communities outside the Web community where the Web page is located) as its neighbor, the probability P (d_ab) that the Web page selects the page b in the Web community a is as follows: $P (d_{ab}) = \frac{d_{ab} + λ}{\sum_{j = 1}^{n_{a}} (d_{aj} + λ)}$ (3)

Where, d_ab is the similarity of the Web page b in the Web community a, n_a means that there are n_a Web pages in the Web community a, and λ is a weighted value, λ ∈ [- k, + ∞). We call this the PDP rule.

As can be seen from Fig. 1, there are three connected Web communities in the original Web, and the Web pages in the community are also connected, as shown in sub-figure (1); a new page is added to the Web with probability 1 - pro, and the Web page joins a Web community according to the WSP principle, and three hyperlinks are introduced into the Web page, two of which are connected with the Web pages in the community with probability pro′ according to the PDP principle, and the remaining hyperlink is connected with the Web pages in other Web communities outside the community with probability 1 - pro′. As shown in sub-figure (2), a new Web community is added to the Web with probability pro, and the Web pages in the new Web community are also connected, and a Web page is randomly selected from the community to connect with three Web pages in other Web communities. The method selected is also the same as in sub-figure (2), as shown in sub-figure (3).

Fig. 1

Evolution Process of Web Community.

After understanding the basic evolution process of the Web community, we need to theoretically analyze the changes in the size and Web page similarity of the Web community that play a decisive role during the evolution of the Web community.

Theorem 1. As the Web changes, the size of the Web community varies with the Web, which shows a power-law distribution.

Prove. The change rate of the size of the Web community a is as follows: $\begin{matrix} \frac{\partial w_{a}}{\partial t} = \frac{w_{a}}{\sum_{i = 1}^{m} w_{i}} \\ = \frac{w_{a}}{\sum_{i = 1}^{m} n_{i} + [(1 - pro) * 1 + pro * n_{a}] * t} \\ \approx \frac{w_{a}}{[(1 - pro) * 1 + pro * n_{a}] * t} \end{matrix}$ (4)

When the Web community a with n_a Web pages joins the Web at t_a, then: $w_{a} (t) = n_{a} * (\frac{t}{t_{a}})^{\frac{1}{1 - pro + pro * n_{a}}}$ (5)

Therefore, the probability P (w_a (t) ⩾ w) that the size of the Web community a is no less than w at t_a is as follows: $P (w_{a} (t) ⩾ w) = P (t_{a} ⩽ t * (\frac{n_{a}}{w})^{1 - pro + pro * n_{a}})$ (6)

We get P (t_a) as follows to obtain the final solution of P (w_a (t) ⩾ w): $P (t_{a}) = \frac{1}{m + pro * t}$ (7)

Then: $P (w_{a} (t) ⩾ w) = \frac{1}{m + pro * t} * (\frac{n_{a}}{w})^{1 - pro + pro * n_{a}}$ (8)

According to the power-law distribution function P (k ⩾ k′) ∼ (k′) ^-γ, Equation (7) satisfies the power-law distribution.

3.2 Change of Web page similarity

The Web page similarity is measured by two parts: 1. the number of hyperlinks between a Web page in the Web community and other pages in the community; 2. The number of hyperlinks between a Web page in the Web community and the Web pages in other Web communities. So we will analyze the change of Web page similarity from the above two parts.

The change of Web page similarity in Web community. When a new Web community is added to the Web with probability pro, the Web page similarity in the existing Web community will not be affected. However, when a new page is added to the Web with probability pro, the new page will first join a Web community a according to the WSP rule, and then select a Web page from the selected Web community as its own neighbor with probabilitypro′ according to the PDP rule.

Theorem 2. As the Web changes, the Web page similarity shows a power-law distribution with the change of the Web size.

Prove. The change rate of the similarity of the Web page b in the Web community a is as follows:

$\begin{matrix} \frac{\partial d_{ab}}{\partial t} = (1 - pro) * {pro}^{'} * k * P (w_{a}) * P (d_{ab}) = \\ \frac{(1 - pro) * {pro}^{'} * k * w_{a} * (d_{ab} + λ)}{\sum_{i = 1}^{m} w_{i} * \sum_{j = 1}^{n_{a}} (d_{aj} + λ)} \end{matrix}$ (9)

$\sum_{j = 1}^{n_{a}} (d_{aj} + λ) = ({\bar{d}}_{a} + {pro}^{'} * k + λ) * w_{a}$ , where, ${\bar{d}}_{a}$ is the average Web page similarity of the Web community a. So Equation (8) is changed to: $\frac{\partial d_{ab}}{\partial t} = \frac{(1 - pro) * {pro}^{'} * k * (d_{ab} + λ)}{({\bar{d}}_{a} + {pro}^{'} * k + λ) * (1 - pro + pro * n_{a}) * t}$ (10)

We assume that new Web communities or new pages are added to the Web at equal intervals, then $P (t_{b}) = \frac{1}{t}$ (11)

As a result, the probability P (d_ab (t) ⩾ c) that the similarity of the Web page b in the Web community is no less than c at t_b is as follows: $\begin{matrix} P (t_{b} ⩽ t * (\frac{{pro}^{'} * k + λ}{c + λ})^{\frac{({\bar{d}}_{a} + {pro}^{'} * k + λ) * (1 - pro + pro * n_{a})}{(1 - pro) * {pro}^{'} * k}}) \\ = (\frac{{pro}^{'} * k + λ}{c + λ})^{\frac{({\bar{d}}_{a} + {pro}^{'} * k + λ) * (1 - pro + pro * n_{a})}{(1 - pro) * {pro}^{'} * k}} \end{matrix}$ (12)

So the distribution probability P (d_ab (t)) of the similarity of the Web page b in the Web community at t_b is as follows: $\begin{matrix} P (d_{ab} (t)) = \frac{({\bar{d}}_{a} + {pro}^{'} * k + λ) * (1 - pro + pro * n_{a})}{(1 - pro) * {pro}^{'} * k} * \\ \frac{({pro}^{'} * k + λ)^{\frac{({\bar{d}}_{a} + {pro}^{'} * k + λ) * (1 - pro + pro * n_{a})}{(1 - pro) * {pro}^{'} * k}}}{(c + λ)^{1 + \frac{({\bar{d}}_{a} + {pro}^{'} * k + λ) * (1 - pro + pro * n_{a})}{(1 - pro) * {pro}^{'} * k}}} \end{matrix}$ (13)

Change in Web page similarity outside the Web community. The Web page similarity inside the Web community is far greater than that outside the Web community. So the Web page similarity outside the Web community can be negligible in the calculation of the Web page similarity in the Web community. Therefore, the similarity of the Web page b is approximately equal to the solution of Equation (12). The distribution of the Web page similarity satisfies the power-law distribution P (z ⩾ z′) ∼ (z′) ^-α. Then, $α = 1 + \frac{({\bar{d}}_{a} + {pro}^{'} * k + λ) * (1 - pro + pro * n_{a})}{(1 - pro) * {pro}^{'} * k}$ .

4 Experimental analysis

4.1 Experimental datasets

We build an experimental simulation platform to verify the effectiveness of the above model. This paper uses Vc++ for programming and SQL database. Experiments were conducted on four real networks, namely Karate Club Network (Karate), United Soccer League Network (Football), E-mail Network of European Research Institutes (Email-EU) and Political Blog Network (Polblogs).

Table 4 shows the attribute information of four real networks, including the number of nodes, edges and communities. Figure 2 shows the Web topology of simulation experiment, a total of 30 Web nodes.

Table 4
Datasets of social networks

Dataset Number of Nodes Number of Edges Number of Communities

Karate 34 78 2

Football 116 616 12

Email-EU 1005 25571 10

Polblogs 1490 16718 4

Dataset	Number of Nodes	Number of Edges	Number of Communities
Karate	34	78	2
Football	116	616	12
Email-EU	1005	25571	10
Polblogs	1490	16718	4

Fig. 2

Experimental Web topology.

4.2 Evaluation index

In most cases, there are no standard results for community discovery. For real datasets, the modularity function proposed by Newman [30] is generally used as an algorithm evaluation index, but the evaluation criterion is not well suitable for overlapping communities. Therefore, on this basis, Shen et al. [31] proposed an overlapping modularity function that can measure the division result of overlapping communities, which is defined as: $EQ = \frac{1}{2 m} \sum_{i} \sum_{u \in C_{i}, v \in C_{i}} \frac{1}{Q_{u} Q_{v}} [A_{uv} - \frac{k_{u} k_{v}}{2 m}]$ (14)

Where, m is the total number of edges in the network, A is the adjacency matrix of the network, k_u is the degree of the node u, and Q_u is the number of communities where the node u is located.

4.4 Experimental results

(1) Test results and analysis on real network datasets.

The proposed improved Web community discovery, HITS, maximal-flow, bipartite directed graph, Fluidc, GN, Louvain and Spectral algorithms were tested on real network datasets, and EQ evaluation index was used to evaluate the community division structure. The test results are shown in Table 5.

Table 5
EQ test results on real network datasets

Algorithm Karate Football Email-EU Polblogs

HITS algorithm 0.1496 0.3585 0.1046 0.0038

Maximal-flow algorithm 0.3424 0.0327 0.1330 0.0884

Bipartite directed graph algorithm 0.3715 0.3534 0.1648 0.1223

Fluidc algorithm 0.2045 0.2415 0.2891 0.3047

GN algorithm 0.3590 0.5510 0.2593 0.3540

Louvain algorithm 0.3025 0.1596 0.1760 0.2967

Spectral algorithm 0.5686 0.3469 0.3054 0.1969

Our algorithm 0.5686 0.5122 0.3813 0.4008

Algorithm	Karate	Football	Email-EU	Polblogs
HITS algorithm	0.1496	0.3585	0.1046	0.0038
Maximal-flow algorithm	0.3424	0.0327	0.1330	0.0884
Bipartite directed graph algorithm	0.3715	0.3534	0.1648	0.1223
Fluidc algorithm	0.2045	0.2415	0.2891	0.3047
GN algorithm	0.3590	0.5510	0.2593	0.3540
Louvain algorithm	0.3025	0.1596	0.1760	0.2967
Spectral algorithm	0.5686	0.3469	0.3054	0.1969
Our algorithm	0.5686	0.5122	0.3813	0.4008

From the test analysis results on real datasets, the proposed algorithm gets the maximum EQ value on the other three datasets except that the EQ value on Football dataset is lower than that of GN algorithm. Spectral algorithm also gets the same maximum EQ value on Karate dataset as the proposed algorithm. To sum up, the community structure of the proposed algorithm is better than that of other community discovery algorithms, which reflects the effectiveness and feasibility of the algorithm.

(2) Test results and analysis on simulation network dataset.

The proposed improved Web community discovery algorithm gets the first Web community from page 15, as shown in the red box in Fig. 3.

Fig. 3

The First Discovered Web Community in Web.

After discovering the first Web community, we get the second Web community from the page 16 outside the community using the improved Web community discovery algorithm, as shown in the triangle in Fig. 4.

Fig. 4

The Second Discovered Web Community in Web.

The performance of various Web community discovery algorithms is compared in Table 6. As can be seen from Table 6, compared with other Web community discovery algorithms, the improved Web community discovery algorithm has obvious advantages: it has linear search time complexity, which can search the Web community from any page in the Web, and is simple and easy to implement.

Table 6

Performance Comparison of Different Web Community Discovery Algorithms

Algorithm	Time Complexity	Need to Determine the Central Web Page
HITS	O(n)	Yes
Maximal-flow	O(n*E²)	No
Bipartite directed graph	O(n\2)	Yes
Fluidc algorithm	O(E)	No
GN algorithm	O(E*n²)	No
Louvain algorithm	O(E*lbn)	No
Spectral algorithm	O(n²)	Yes
Our algorithm	O(E)	No

In addition, a Web community a with the size w_a is added to the Web of the simulation platform with probability pro in the simulation experiment. After 1000 steps, we get the cumulative distribution data of the Web community a, as shown in Tables 7 –10.

Table 7

The result of P (w_a (t) ⩾ w) when w_a = 6

pro	w = 1	w = 2	w = 3	w = 4	w = 5	w = 6	w = 7	w = 8	w = 9	w = 10
0.1	0.0509	0.0277	0.0180	0.0129	0.0098	0.0078	0.0064	0.0053	0.0046	0.0039
0.5	0.0932	0.0225	0.0082	0.0038	0.0020	0.0012	0.0007	0.0005	0.0003	0.0002
0.9	0.4666	0.0502	0.0103	0.0030	0.0011	0.0005	0.0002	0.0001	0.0000	0.0000

Table 8

The result of P (w_a (t) ⩾ w) when w_a = 7

pro	w = 1	w = 2	w = 3	w = 4	w = 5	w = 6	w = 7	w = 8	w = 9	w = 10
0.1	0.2206	0.0728	0.0380	0.0240	0.0168	0.0125	0.0098	0.0079	0.0066	0.0055
0.5	1.0000	0.2989	0.0590	0.0187	0.0077	0.0037	0.0020	0.0012	0.0007	0.0005
0.9	1.0000	1.0000	0.2511	0.0398	0.0096	0.0030	0.0011	0.0005	0.0002	0.0001

Table 9

The result of P (w_a (t) ⩾ w) when w_a = 8

pro	w = 1	w = 2	w = 3	w = 4	w = 5	w = 6	w = 7	w = 8	w = 9	w = 10
0.1	0.3362	0.1035	0.0519	0.0319	0.0218	0.0160	0.0123	0.0098	0.0080	0.0067
0.5	1.0000	1.0000	0.1645	0.0451	0.0165	0.0073	0.0036	0.0020	0.0012	0.0007
0.9	1.0000	1.0000	0.6578	0.0968	0.0198	0.0058	0.0019	0.0008	0.0003	0.0001

Table 10

The result of P (w_a (t) ⩾ w) when w_a = 8

pro	w = 1	w = 2	w = 3	w = 4	w = 5	w = 6	w = 7	w = 8	w = 9	w = 10
0.1	0.1470	0.0708	0.0422	0.0282	0.0203	0.0154	0.0121	0.0098	0.0081	0.0068
0.5	1.0000	0.4841	0.1149	0.0376	0.0151	0.0070	0.0036	0.0020	0.0012	0.0007
0.9	1.0000	1.0000	0.8564	0.1374	0.0308	0.0087	0.0029	0.0011	0.0005	0.0002

From the data in Tables 7 –10, we can see that the Web pages with high similarity always attract those with low similarity to join their own Web communities, so their Web pages are lost when a new Web community enters the Web, that is to say, when a new Web community joins the Web, it will be torn apart by other existing Web communities, and the fragmented Web pages are then added to the corresponding Web communities, resulting in the increase of information in the existing Web community and the decrease of information in the new Web community, or even disappearance in the Web.

Assuming that the Web page b is connected with the Web pages in the Web community a with probability pro′, we got the cumulative distribution data of the Web page similarity of the Web community, as shown in Tables 11–12.

Table 11

The result of P (d) when pro = 0.1

pro ’	c = 2	c = 3	c = 4	c = 5	c = 6	c = 7	c = 8	c = 9	c = 10
0.3	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000
0.5	0.1870	0.0038	0.0004	0.0001	0.0000	0.0000	0.0000	0.0000	0.0000
0.9	1.0000	1.0000	0.1460	0.0366	0.0125	0.0052	0.0025	0.0013	0.0007

Table 12

The result of P (d) when pro = 0.2

pro ’	c = 2	c = 3	c = 4	c = 5	c = 6	c = 7	c = 8	c = 9	c = 10
0.3	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000
0.5	0.0258	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000
0.9	1.0000	1.0000	0.0466	0.0049	0.0008	0.0002	0.0001	0.0000	0.0000

From the data in Tables 11–12, we can see that the probability pro′ is proportional to the similarity of the new page. Figure 5 shows the cumulative distribution of the Web page similarity, where (a) and (b) represent pro = 0.1 and pro = 0.2, respectively. As can be seen from the figure, the change in the similarity of the new page satisfies the power-law distribution. Equation (13) shows that the similarity of a new page is proportional to the size of Web community that the new page chooses to join. Therefore, if a new page joins the largest Web community according to the WSP and PDP rules and tries to be a neighbor of the Web page with the highest similarity in the community, then the similarity of the new page will reach the highest level. The more opportunities it has to spread its information in the Web community, the more likely it is to be noticed, and vice versa.

Fig. 5

The Cumulative Distribution of Web Page Similarity.

5 Conclusions

This paper proposes to reduce the time complexity of the Web community discovery using the attraction between Web pages. The proposed algorithm treats each Web page in the Web pages collection as an individual with attraction, elaborates the discovery process of the Web community from a Web page in the Web pages collection, and introduces the WSP and PDP rules to explain the basic evolution process of the Web community. Finally, we build an experimental platform to analyze the specific discovery process of the Web community in detail. Experimental results show that the attraction between Web pages is employed during the discovery of the Web community, and the complexity of search time is linear, and there is no need to determine the Web page of authority center, and the performance is far better than the existing algorithms. The change in the similarity of the new page satisfies the power-law distribution, and the similarity of a new page is proportional to the size of the Web community that the new page chooses to join. According to various data of Web community evolution, we always obey the WSP and PDP rules to some extent during the evolution of the Web community, so that more users can focus on the information.

Footnotes

Acknowledgments

This research was supported by Open Fund of Articial Intelligence Key Laboratory of Sichuan Province under Grant No.2020RYJ01, and supported by Supported by Innovation Team of Chengdu Normal University under Grant No. CSCXTD2020B09.

References

, Bai

, Zhang

, Tang

and Luo

, Opinion community detection and opinion leader detection based on text information and network topology in cloud environment, Information Sciences 504 (2019), 61–83.

Gupta

and Kumar

, An overlapping community detection algorithm based on rough clustering of links, Data & Knowledge Engineering 2019, 101777.

Gao

and Zhu

, Link prediction based on the powerful combination of endpoints and neighbors, International Journal of Modern Physics B 34(28) (2020), 2050269.

Chen

Y.Y.

and Ye

, Community leader and transition probability based LPA, International Journal of Modern Physics B 34(27) (2020), 2050253.

, Cai

, Meng

, Chen

, Deng

and Cao

, Parallel community detection based on distance dynamics for large-scale network, IEEE Access 6 (2018), 42775–42789.

Tummarello

and Morbidoni

, The DBin platform: A complete environment for Semantic Web Communities, Journal of Web Semantics 6(4) (2008), 257–265.

Andraz

, Gregor

and Lozar

M.K.

, The effect of email invitation elements on response rate in a web survey within an online community, Computers in Human Behavior 56 (2016), 320–329.

Xian

, Zhao

, Sheng

V.S.

, Fang

, Gu

, Yang

and Cui

, Stratification-Based Outlier Detection over the Deep Web, Computational Intelligence and Neuroscience 2016, 7386517.

Chang

B.-W.

, In-place editing of Web pages: Sparrow community-shared documents, Computer Networks and ISDN Systems 30 (1998), 489–498.

10.

, Liu

and Feng

, On the Spectral Characterization and Scalable Mining of Network Communities, IEEE Transactions on Knowledge and Data Engineering 24(2) (2012), 326–337.

11.

Gibson

, Kleinberg

and Raghavan

, Inferring Web Communities from Link Topology[C], In, Proceedings of the 9th ACM Conference on Hypertext and Hypermedia, ACM 1998, 225–234.

12.

Flake

, Efficient Identification of Web Communities[C], Acm Sigkdd International Conference on Knowledge Discovery & Data Mining 2000, 150–160.

13.

Kumar

, Raghavan

, Rajagopalan

and Tomkins

, Extracting Large-Scale Knowledge Bases from the Web[C], In, Proceedings of the 25th International Conference on Very Large Data Bases, Morgan Kaufmann 1999, 639–650.

14.

Reddy

and Kitsuregawa

, Inferring Web Communities Through Relaxed Cocitation and Dense Bipartite Graphs[C], In Proceedings of Data Base Engineering Workshop (2002).

15.

Eustace

, Wang

and Li

, Approximating web communities using subspace decomposition, Knowledge-Based Systems 70 (2014), 118–127.

16.

Murata

, Visualizing the structure of Web communities based on data acquired from a search engine, IEEE Transactions on Industrial Electronics 50(5) (2003), 860–866.

17.

Velardi

, Cucchiarelli

and Petit

, A Taxonomy Learning Method and Its Application to Characterize a Scientific Web Community, IEEE Transactions on Knowledge and Data Engineering 19(2) (2007), 180–191.

18.

Paliouras

, Discovery of Web user communities and their role in personalization, User Modeling and User-Adapted Interaction 22 (2012), 151–175.

19.

Tzekina

, Danthi

and Rockmore

D.N.

, Evolution of community structure in the world trade web, The European Physical Journal B 63 (2008), 541–545.

20.

Jingyu

, Kejia

and Jianing

, Web article quality ranking based on web community knowledge, Computing 97 (2015), 509–537.

21.

Duan

X.Y.

, Yuan

and Meng

F.R.

, Dynamic community detection: A survey, Journal of Frontiers of Computer Science and Technology 3(10) (2020), 1–19.

22.

Cazabet

, Amblard

and Hanachi

, Detection of overlapping communities in dynamical social networks, MN, USA: IEEE, Proceedings of 2010 IEEE Second International Conference on Social Computing. Minneapolis 2010, 309–314.

23.

Agarwal

, Verma

, Agarwal

, et al., DyPerm: Maximizing permanence for dynamic community detection, Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Cham 2018, 437–449.

24.

Cordeiro

, Sarmento

R.P.

and Gama

, Dynamic community detection in evolving networks using locality modularity optimization, Social Network Analysis and Mining 6(1) (2016), 15.

25.

Duan

, Li

, et al., Incremental K-clique clustering in dynamic social networks, Artificial Intelligence Review 38(2) (2012), 129–147.

26.

Xin

, Xie

and Yang

, The adaptive dynamic community detection algorithm based on the non-homogeneous random walking, Physica A-statistical Mechanics and Its Applications 450 (2016), 241–252.

27.

Sattari

and Zamanifar

, A cascade information diffusion based label propagation algorithm for community detection in dynamic social networks, Journal of Computational Science 25 (2018), 122–133.

28.

and Chen

, A fast algorithm for community detection in temporal network, Physica A: Statistical Mechanics and its Applications 429 (2015), 87–94.

29.

Blondel

V.D.

, Guillaume

J.L.

, Lambiotte

, et al., Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment 2008(10) (2008), P10008.

30.

Newman

M.E.J.

and Girvan

, Finding and evaluating community structure in networks, Physical Review E 69(2) (2004), 026113.

31.

Shen

H.W.

, Cheng

X.Q.