Biomedical subjects

B Kahng

Publications and source records attributed to B Kahng.

At least 19 recordsLinked to original sources

PubMed2006

Network analysis of online bidding activity.

With the advent of digital media, people are increasingly resorting to online channels for commercial transactions. The online auction is a prototypical example. In such online transactions, the pattern of bidding activity is more complex than traditional offline 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 to a traditional classification scheme. The implication of the difference between the two is discussed.

Journal Article↗

PubMed2006

Structure and evolution of online social relationships: Heterogeneity in unrestricted discussions.

With the advancement in the information age, people are using electronic media more frequently for communications, and social relationships are also increasingly resorting to online channels. While extensive studies on traditional social networks have been carried out, little has been done on online social networks. Here we analyze the structure and evolution of online social relationships by examining the temporal records of a bulletin board system (BBS) in a university. The BBS dataset comprises of 1908 boards, in which a total of 7446 students participate. An edge is assigned to each dialogue between two students, and it is defined as the appearance of the name of a student in the from- and to-field in each message. This yields a weighted network between the communicating students with an unambiguous group association of individuals. In contrast to a typical community network, where intracommunities (intercommunities) are strongly (weakly) tied, the BBS network contains hub members who participate in many boards simultaneously but are strongly tied, that is, they have a large degree and betweenness centrality and provide communication channels between communities. On the other hand, intracommunities are rather homogeneously and weakly connected. Such a structure, which has never been empirically characterized in the past, might provide a new perspective on the social opinion formation in this digital era.

Journal Article↗

PubMed2006

Bidding process in online auctions and winning strategy: Rate equation approach.

Online auctions have expanded rapidly over the last decade and have become a fascinating new type of business or commercial transaction in this digital era. Here we introduce a master equation for the bidding process that takes place in online auctions. We find that the number of distinct bidders who bid k times up to the tth bidding progresses, called the k-frequent bidder, seems to scale as n(k)(t) approximately tk(-2.4). The successfully transmitted bidding rate by the k-frequent bidder is likely to scale as q(k)(t) approximately k(-1.4), independent of t for large t. This theoretical prediction is close to empirical data. These results imply that bidding at the last moment is a rational and effective strategy to win in an eBay auction.

Journal Article↗

PubMed2006

Skeleton and fractal scaling in complex networks.

We find that the fractal scaling in a class of scale-free networks originates from the underlying tree structure called a skeleton, a special type of spanning tree based on the edge betweenness centrality. The fractal skeleton has the property of the critical branching tree. The original fractal networks are viewed as a fractal skeleton dressed with local shortcuts. An in silico model with both the fractal scaling and the scale-invariance properties is also constructed. The framework of fractal networks is useful in understanding the utility and the redundancy in networked systems.

Escherichia coli↗

PubMed2005

Extremal dynamics on complex networks: analytic solutions.

The Bak-Sneppen model displaying punctuated equilibria in biological evolution is studied on random complex networks. By using the rate equation and the random walk approaches, we obtain the analytic solution of the fitness threshold xc to be 1/((k)f+1), where (k)f=(k2)/(k) (=(k)) in the quenched (annealed) updating case, where kn is the nth moment of the degree distribution. Thus, the threshold is zero (finite) for the degree exponent gamma<3 (gamma>3) for the quenched case in the thermodynamic limit. The theoretical value xc fits well to the numerical simulation data in the annealed case only. Avalanche size, defined as the duration of successive mutations below the threshold, exhibits a critical behavior as its distribution follows a power law, Pa(s) approximately s(-3/2).

Journal Article↗

PubMed2005

Modular synchronization in complex networks.

We study the synchronization transition (ST) of a modified Kuramoto model on two different types of modular complex networks. It is found that the ST depends on the type of intermodular connections. For the network with decentralized (centralized) intermodular connections, the ST occurs at finite coupling constant (behaves abnormally). Such distinct features are found in the yeast protein interaction network and the Internet, respectively. Moreover, by applying the finite-size scaling analysis to an artificial network with decentralized intermodular connections, we obtain the exponent associated with the order parameter of the ST to be beta approximately 1 different from beta(MF) approximately 1/2 obtained from the scale-free network with the same degree distribution but the absence of modular structure, corresponding to the mean field value.

Journal Article↗

PubMed2005

Nonlocal evolution of weighted scale-free networks.

We introduce the notion of globally updating evolution for a class of weighted networks, in which the weight of a link is characterized by the amount of data packet transport flowing through it. By noting that the packet transport over the network is determined nonlocally, this approach can explain the generic nonlinear scaling between the strength and the degree of a node. We demonstrate by a simple model that the strength-driven evolution scheme recently introduced can be generalized to a nonlinear preferential attachment rule, generating the power-law behaviors in degree and in strength simultaneously.

Journal Article↗

PubMed2005

Load distribution in weighted complex networks.

We study the load distribution in weighted networks by measuring the effective number of optimal paths passing through a given vertex. The optimal path, along which the total cost is minimum, crucially depends on the cost distribution function p(c) (c) . In the strong disorder limit, where p(c) (c) approximately c(-1) , the load distribution follows a power law both in the Erdös-Rényi (ER) random graphs and in the scale-free (SF) networks, and its characteristics are determined by the structure of the minimum spanning tree. The distribution of loads at vertices with a given vertex degree also follows the SF nature similar to the whole load distribution, implying that the global transport property is not correlated to the local structural information. Finally, we measure the effect of disorder by the correlation coefficient between vertex degree and load, finding that it is larger for ER networks than for SF networks.

Journal Article↗

PubMed2005

Spin-glass phase transition on scale-free networks.

We study the Ising spin-glass model on scale-free networks generated by the static model using the replica method. Based on the replica-symmetric solution, we derive the phase diagram consisting of the paramagnetic (P), ferromagnetic (F), and spin glass (SG) phases as well as the Almeida-Thouless line as functions of the degree exponent lambda, the mean degree K, and the fraction of ferromagnetic interactions r. To reflect the inhomogeneity of vertices, we modify the magnetization m and the spin-glass order parameter q with vertex- weights. The transition temperature T(c) (T(g)) between the P-F (P-SG) phases and the critical behaviors of the order parameters are found analytically. When 2 1/2, while it is in the SG phase at r=1/2. m and q decay as power-laws with increasing temperature with different lambda-dependent exponents. When lambda>3, the T(c) and T(g) are finite and related to the percolation threshold. The critical exponents associated with m and q depend on lambda for 3<lambda<5 (3<lambda<4) at the P-F (P-SG) boundary.

Journal Article↗

PubMed2005

Robustness of the avalanche dynamics in data-packet transport on scale-free networks.

We study the avalanche dynamics in the data-packet transport on scale-free networks through a simple model. In the model, each vertex is assigned a capacity proportional to the load with the proportionality constant 1+a . When the system is perturbed by a single vertex removal, the load of each vertex is redistributed, followed by subsequent failures of overloaded vertices. The avalanche size depends on the parameter a as well as which vertex triggers it. We find that there exists a critical value a(c) at which the avalanche size distribution follows a power law. The critical exponent associated with it appears to be robust as long as the degree exponent is between 2 and 3 and is close in value to that of the distribution of the diameter changes by single vertex removal.

Journal Article↗

PubMed2004

Kinetic roughening of ion-sputtered Pd(001) surface: beyond the Kuramoto-Sivashinsky model.

We investigate the kinetic roughening of Ar+ ion-sputtered Pd(001) surface both experimentally and theoretically. In situ real-time x-ray reflectivity and in situ scanning tunneling microscopy show that nanoscale adatom islands form and grow with increasing sputter time t. Surface roughness W(t) and lateral correlation length xi(t) follow the scaling laws W(t) approximately t(beta) and xi(t) approximately t(1/z) with the exponents beta approximately 0.20 and 1/z approximately 0.20, for an ion beam energy epsilon=0.5 keV, which is inconsistent with the prediction of the Kuramoto-Sivashinsky (KS) model. We thereby extend the KS model by applying the coarse-grained continuum approach of the Sigmund theory to the order of O(inverted Delta(4),h(2)), where h is the surface height, and derive a new term of the form inverted Delta(2)(inverted Delta h)(2) which plays a decisive role in describing the observed morphological evolution of the sputtered surface.

Journal Article↗

PubMed2003

Sandpile on scale-free networks.

We investigate the avalanche dynamics of the Bak-Tang-Wiesenfeld sandpile model on scale-free (SF) networks, where the threshold height of each node is distributed heterogeneously, given as its own degree. We find that the avalanche size distribution follows a power law with an exponent tau. Applying the theory of the multiplicative branching process, we obtain the exponent tau and the dynamic exponent z as a function of the degree exponent gamma of SF networks as tau=gamma divided by (gamma-1) and z=(gamma-1) divided by (gamma-2) in the range 2 3, with a logarithmic correction at gamma=3. The analytic solution supports our numerical simulation results. We also consider the case of a uniform threshold, finding that the two exponents reduce to the mean-field ones.

Journal Article↗

PubMed2003

Probabilistic prediction in scale-free networks: diameter changes.

In complex systems, responses to small perturbations are too diverse to definitely predict how much they would be, and then such diverse responses can be predicted in a probabilistic way. Here we study such a problem in scale-free networks, for example, the diameter changes by the deletion of a single vertex for various in silico and real-world scale-free networks. We find that the diameter changes are indeed diverse and their distribution exhibits an algebraic decay with an exponent zeta asymptotically. Interestingly, the exponent zeta is robust as zeta approximately 2.2(1) for most scale-free networks and insensitive to the degree exponents gamma as long as 2<gamma</=3. However, there is another type with zeta approximately 1.7(1) and its examples include the Internet and its related in silico model.

Growth↗

PubMed2003

Emerging behavior in electronic bidding.

We characterize the statistical properties of a large number of agents on two major online auction sites. The measurements indicate that the total number of bids placed in a single category and the number of distinct auctions frequented by a given agent follow power-law distributions, implying that a few agents are responsible for a significant fraction of the total bidding activity on the online market. We find that these agents exert an unproportional influence on the final price of the auctioned items. This domination of online auctions by an unusually active minority may be a generic feature of all online mercantile processes.

Journal Article↗

PubMed2003

Betweenness centrality correlation in social networks.

Scale-free (SF) networks exhibiting a power-law degree distribution can be grouped into the assortative, dissortative, and neutral networks according to the behavior of the degree-degree correlation coefficient. Here we investigate the betweenness centrality (BC) correlation for each type of SF networks. While the BC-BC correlation coefficients behave similarly to the degree-degree correlation coefficients for the dissortative and neutral networks, the BC correlation is nontrivial for the assortative ones found mainly in social networks. The mean BC of neighbors of a vertex with BC g(i) is almost independent of g(i), implying that each person is surrounded by almost the same influential environments of people no matter how influential the person may be.

Journal Article↗

PubMed2002

Infinite-order percolation and giant fluctuations in a protein interaction network.

We investigate a model protein interaction network whose links represent interactions between individual proteins. This network evolves by the functional duplication of proteins, supplemented by random link addition to account for mutations. When link addition is dominant, an infinite-order percolation transition arises as a function of the addition rate. In the opposite limit of high duplication rate, the network exhibits giant structural fluctuations in different realizations. For biologically relevant growth rates, the node degree distribution has an algebraic tail with a peculiar rate dependence for the associated exponent.

Journal Article↗

PubMed2002

Robustness of the in-degree exponent for the World-Wide Web.

We consider a stochastic model for directed scale-free networks following power laws in the degree distributions in both incoming and outgoing directions. In our model, the number of vertices grow geometrically with time with a growth rate p. At each time step, (i) each newly introduced vertex is connected to a constant number of already existing vertices with the probability linearly proportional to in-degree distribution of a selected vertex, and (ii) each existing vertex updates its outgoing edges through a stochastic multiplicative process with mean growth rate of outgoing edges g and its variance sigma(2). Using both analytic treatment and numerical simulations, we show that while the out-degree exponent gamma(out) depends on the parameters, the in-degree exponent gamma(in) has two distinct values, gamma(in)=2 for p>g and 1 for p<g, independent of different parameters values. The latter case has logarithmic correction to the power law. Since the vertex growth rate p is larger than the degree growth rate g for the World-Wide Web (WWW) nowadays, the in-degree exponent appears robust as gamma(in)=2 for the WWW.

Journal Article↗

PubMed2002

Geometric fractal growth model for scale-free networks.

We introduce a deterministic model for scale-free networks, whose degree distribution follows a power law with the exponent gamma. At each time step, each vertex generates its offspring, whose number is proportional to the degree of that vertex with proportionality constant m-1 (m>1). We consider the two cases: First, each offspring is connected to its parent vertex only, forming a tree structure. Second, it is connected to both its parent and grandparent vertices, forming a loop structure. We find that both models exhibit power-law behaviors in their degree distributions with the exponent gamma = 1+ln(2m-1)/ln m. Thus, by tuning m, the degree exponent can be adjusted in the range, 2 < gamma < 3. We also solve analytically a mean shortest-path distance d between two vertices for the tree structure, showing the small-world behavior, that is, d approximately ln N/ln K macro, where N is system size, and k macro is the mean degree. Finally, we consider the case that the number of offspring is the same for all vertices, and find that the degree distribution exhibits an exponential-decay behavior.

Journal Article↗