{'fraction_non_alphanumeric': 0.03200287666307084, 'fraction_numerical': 0.00982859882536258, 'mean_word_length': 4.758109040717736, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Network analysis of online bidding activity

With the advent of digital media, people are increasingly resorting to online channels for commercial transactions. Online auction is a prototypical example. In such online transactions, the pattern of bidding activity is more complex than traditional online transactions; this is because the number of bidders participating in a given transaction is not bounded and the bidders can also easily respond to the bidding instantaneously. By using the recently developed network theory, we study the interaction patterns between bidders (items) who (that) are connected when they bid for the same item (if the item is bid by the same bidder). The resulting network is analyzed by using the hierarchical clustering algorithm, which is used for clustering analysis for expression data from DNA microarrays. A dendrogram is constructed for the item subcategories; this dendrogram is compared with a traditional classification scheme. The implication of the difference between the two is discussed.


I. INTRODUCTION
Electronic commerce (e-commerce) refers to any type of business of commercial transaction that involves information transfer across the Internet. Online auction, a synergetic combination of the Internet supported by instantaneous interactions and traditional auction mechanisms, has rapidly expanded over the last decade. Owing to this rapid expansion and the importance of online auctions, very recently researchers have begun to pay attention to the various aspects of online auctions [1,2,3,4,5,6,7]. According to recent studies based on empirical data obtained from eBay.com, it was discovered that the online auction system is driven by a self-organized process, involving almost all the agents that participate in a given auction activity. For example, the total number of bids placed for a single item or category and the bid frequency submitted by each agent follow power-law distributions [5]. Further, the bidding process occurring in online auctions has been successfully described through the stochastic rate equation [6]. Thus, understanding of the bidding activities in online auctions is a highly attractive topic for the statistical physics community.
The remarkable connection between beer and diapers discovered in 1992 by Blischok et al. [8] has significantly improved profits. They analyzed the correlation between items sold at a drug store during a particular time interval between 5 p.m. and 7 p.m.. They found a strong correlation between the two items, which had never been noticed by the retailer earlier. This correlation arises from the fact that fathers in families tend to buy beer when they are told by their wives to buy diapers while returning home. This discovery, which is considered as a pioneering work of data mining, compelled drug stores to redesign their displays; this resulted in an increase in beer sales.
In online auctions, most of the limitations hampering traditional offline auctions, such as spatial and temporal constraint have virtually disappeared. Thus, it would be interesting to investigate how the bidding pattern of online auctions has changed from the traditional one. On the other hand, recently, considerable attention have been focused on complex network problems as an interdisciplinary subject [9,10,11]. Diverse computational methods to find clusters within largescale networks have been introduced (for example, see Refs. [12,13,14,15,16]). Thus, by combining these two issues, in this study, we investigate the pattern emerging from the interactions between individual bidders or items in online auctions by using the recently developed network theory. The resulting network provides information on the bidding pattern of individual bidders as well as the correlation between different item subcategories. Moreover, we construct a dendrogram for these subcategories and compare it with a traditional classification scheme based on off-line transactions. For the purpose, we use an algorithm applied for clustering analysis for the expression data from a DNA microarray experiment in biological systems [17]. The dendrogram thus obtained is consumer-oriented, reflecting the pattern of an individual bidder's activities. Thus, it can be used for increasing profits by providing consumers with a link between the items, which should interest the consumers.
Our study is based on empirical data [5] collected from http://www.eBay.com. The dataset comprises all the auctions that ended in a single day, July 5, 2001, and includes 264,073 auctioned items grouped into 18 categories and 192 subcategories. The number of distinct agents that participated in these merchandize was 384,058.

II. TOPOLOGIES OF BIDDER AND ITEM NETWORKS
The data contain the information on which bidder bids for which item via their unique user ID. Thus, we can construct a bipartite network comprising two disjoint sets of vertices, bidders and items, as shown in Fig. 1. The bipartite network can be converted to a single species of network such as the bidder or the item network, as shown in Figs. 2(a) and 2(b), respectively. The bidder and item networks can have edges with weight. For example, bidders C and D in Fig. 1 are connected twice through items a and c. Hence, the edge between C and D has weight 2. Similarly, items a and b are connected twice through bidders C and E. Thus, the edge between vertices a and b in the item network has weight 2. Statistics describing the topology of the entire network and the giant component of the bidder and the item network are listed in Table I  and Table II, respectively.
Next, we characterize the structure of the bidder and item networks. First, we regard each network as a binary network, neglecting the weight of each edge. The network configuration can be described by the adjacent matrix {a ij }; its component is 1 when two vertices i and j are connected and 0 otherwise. Then, degree k i of vertex i is k i = N j a ij , which is the number of edges connected to it. We find that the degree distribution exhibits a power-law behavior asymptotically for both the bidder and item networks, P d (k) ∼ k −γ . The degree exponent   γ is estimated to be γ B ≈ 3.0 for the bidder network and γ I ≈ 2.0 for the item network, as shown in Fig. 3. Second, strength s i of vertex i is the sum of the weights of each edge connected to it. That is, s i = N j a ij w ij , where w ij is the weight of the edge between vertices i and j. The strength distributions of the bidder and item networks also exhibit power-law behaviors asymptotically as P s (s) ∼ (s + s 0 ) −η where η B ≈ 4.0 for the bidder network and η I ≈ 3.5 for the item network, as shown in Fig. 4. s 0 is constant. Strength and degree of a given vertex exhibit an almost linear relationship s(k) ∼ k ζ with ζ ≈ 0.95; however, large fluctuations are observed for large k in Fig. 5.
Third, we measure the mean nearest-neighbor degree function k nn (k). The mean degree of the nearestneighbor vertices of a given vertex i with degree k is measured as follows: The average of k i,nn over the centered vertex with degree  The exponent is estimated to be ηB ≈ 4.0 for the bidder network and ηI ≈ 3.5 for the item network. s0 = 51 is used for the bidder network and s0 = 52 for the item network.  k is taken to obtain k nn (k). For the weighted network, formula (1) is replaced following the formula [18]: From this equation, k (w) nn (k) can be similarly obtained. It is found that the functions k nn (k) and k (w) nn (k) increase with the degree k of the centered vertex for both the bidder and item networks irrespective of the binary or weighted versions. That is, both the networks are assortatively mixed, implying that active bidders tend to simultaneously bid for common items, thereby attractive items are also connected via such active bidders.
Fourth, the local clustering coefficient c i is the density of transitive relationships, and is defined as the number of triangles formed by its neighbors, which are cornered at vertex i, divided by the maximum possible number of neighbors, k i (k i − 1)/2. That is, The average of c i over the vertices with degree k is called the clustering coefficient function c(k). For weighted networks, a similar clustering coefficient c The average of c (w) i over the cornered vertices with degree k is similarly defined and denoted as c (w) (k). For the bidder network, the clustering coefficient functions c(k) and c (w) (k) decrease with respect to k as shown in Fig.7(a); they exhibit large fluctuations for large k, implying that the bidder network is hierarchically organized. For the item network, however, both c(k) and c (w) (k) are almost independent of k, which is shown in Fig. 7(b); this implies that the network is almost randomly organized. Such behaviors are observed irrespective of whether the networks are binary or weighted.

III. CLUSTER IDENTIFICATION
By using network analysis, individual elements can be classified into clusters. Here, we apply the hierarchical agglomeration (HA) algorithm, which was introduced by Clauset et al. [19], to the item network containing 264,073 items. In particular, the algorithm is useful for a system containing a large number of elements. Clusters identified using this analysis are compared with traditional subcategories established based on off-line transactions. The obtained difference can be used for reorganizing a dendrogram with regard to item subcategories; this difference reflects the pattern of online bidding activities.
To realize this, we first store the topology of the item network by using the adjacent matrix {a ij }. By maintaining this information, we delete all the edges, thereby leaving N isolated vertices. At each step, we select one edge from the stored adjacent matrix, which maximizes a change in the modularity, defined as where e αα is the fraction of the edges that connect the vertices within cluster α on both the ends of each edge, and a α is the fraction of edges attached on one end or both the ends to vertices within cluster α. The selected edge is eliminated from the stored matrix. We continue this edge-adding process until the modularity becomes maximum. We find that the modularity reaches the value Q max ≈ 0.79 for the item network and Q max ≈ 0.83 for the bidder network; this implies that both the networks are extremely well categorized. We recognize 1,904 and 870 distinct clusters in the bidder and item networks, respectively. The cluster sizes, the number of vertices of

A. Closeness
In this section, we focus on the item network. We have identified 870 distinct clusters by using the clustering algorithm. Among them, 49 clusters contain more than 100 items within each cluster. On the other hand, according to the traditional classification scheme, items in the eBay auction are categorized into 18 categories which contains 192 subcategories. Obviously the clusters that we found are not equivalent to these categories or subcategories. Thus, our goal is to construct a new dendrogram, a hierarchical tree, among 192 subcategories based on the closeness between the obtained clusters and the existing subcategories.
To illustrate closeness, we select a cluster α and classify the items within the cluster into 192 subcategories. The fraction of items in each subcategory µ is the closeness C αµ . For example, Fig. 10 shows the closenesses for the first five largest clusters. Each strip represents a cluster obtained from the HA algorithm. For each strip, the x-axis represents 192 subcategories, and the y-axis does the closeness. The bar indicates the closeness. For cluster 1, subcategory (a) exhibits the largest closeness. For cluster 2. subcategory (c) has the largest closeness, and so on. The abbreviations for the 18 main categories are as follows: Antique stands for antiques and art; Biz, business and office; Clothes, clothing and accessories; Collect, collectibles; Comp, computers; Elec, consumer electronics; Dolls, dolls and bears; Home, home and garden's; Jewelry, jewelry, gemstones and watches; Glass, pottery and glass; and Estt, real estate.

B. Correlation matrix
To quantify the correlation, we adopt the method used for the clustering analysis for expression data from DNA microarrays. In this approach, we regard the closeness as the expression level, subcategories as genes, and clusters as different DNA microarray experiments [17].
Based on the correlation matrix, a dendrogram that assembles all n = 194 subcategories into a single tree can be constructed. For this purpose, we use the hierarchical clustering algorithm introduced by Eisen et al. [17]. We start the tree construction process by calculating the correlation coefficients {ρ αβ } with size 192 × 870. Next, the matrix is scanned to identify a pair of subcategories with the highest value of the correlation coefficient, and the two subcategories are combined. Thus, a pseudo-subcategory is created, and its closeness profile is calculated only by averaging closenesses of the combined subcategories. This is referred to as the average-linkage clustering method. Then, n − 2 isolated subcategories and a pseudo-subcategory remain. The correlation matrix is updated with these n − 1 units and the highest correlation coefficient is found. The process is repeated n − 1 times until only a single element remains. After these steps, a dendrogram is constructed in which the height represents the magnitude of the correlation coefficient.

C. Rearrangement of subcategories in the dendrogram
The resulting dendrogram is shown in the upper part of Fig. 11, which is considerably different from the traditional classification scheme shown in the lower part of this figure. We discuss the details of the correlations of the subcategories in the dendrogram. For discussion, we divide the entire tree structure into six branches, denoted by (A)-(F).
To be specific, branch (A) covers a broad range of different collectibles. The relationship between the subcategories may be attributed to collecting manias. Branch (B) mainly covers three types of subcategories: clothing and accessories, business, office and industries, and sports categories. Branch (C) consists of three parts: the first part has antiquary property and the items used for decorating homes and the second part covers very broad kinds of items. The third is interesting and covers a set of electronic products such as computers, cameras, audio players, etc. It also includes video games as well as food and beverages. At a glance, one may wonder how these two items are correlated; however, by considering the fact that some video games maniacs requires foods and beverages while playing, one can find the reason. Thus, the dendrogram indeed reflects the bidding patterns of individual bidders. Branch (D) covers items related to artistic collections and hobbies. Branch (E) covers books, dolls for children, etc. Finally, branch (F) mainly covers collectibles in a wide range from jewelry to stamps.

V. CONCLUSIONS AND DISCUSSION
Based on the empirical data collected from the eBay web site, we have constructed a bipartite network comprising bidders and items. The bipartite network is converted into two single species of networks, the bidder and item networks. We measured various topological properties of each network. Both networks are scale free in the degree distribution. It is noteworthy that both the networks are assortatively mixed with regard to the degree correlation. This fact implies that the active bidders tend to simultaneously bid for common items; therefore, they are connected. Accordingly, attractive items are connected via such active bidders. Next, by applying the hierarchical agglomeration algorithm, we identified clusters in the bidder and item networks. The clusters are well separated from each other. Then, we calculate the correlation matrix between subcategories by using the information on the fraction of items in each subcategory in a given cluster. By using this correlation  matrix, we construct the dendrogram, which is different from the traditional classification scheme. Based on a detailed investigation about the items closely located in the dendrogram, we find that the dendrogram indeed is bidder-oriented in an online auction. Therefore, the dendrogram could be useful for marketing renovation, resulting in an increase in profits. For visual clarity, however, the bilayer structure is shown in a multilayer manner. For comparison, the subcategories are in the same order as that used in the upper part. We can easily observe that the traditional classification scheme is entangled from the bidder-oriented perspective.