Complex Networks: A Review - Ijcaonline
International Journal of Computer Applications (0975 – 8887)Volume 101– No.15, September 2014Complex Networks: A ReviewKriti SharmaMinni AhujaStudent - M.tech (CSE)Astt. Prof. – M.tech (CSE)CSE Dept., Guru Nanak Dev University,RC Gurdaspur, IndiaCSE Dept., Guru Nanak Dev University,RC Gurdaspur, IndiaABSTRACTIn late 1950s, two mathematicians discovered a network withcomplex topology by random graph theory. Complex networkshave received great attention in past few decades. Many studieshave been done on complex networks and many are still inprogress. Complex Networks are the networks which can beseen in real as well as in technological systems. They havenodes and these nodes are connected by various links. They arecalled complex networks because of the underlying complexarchitecture and complex topology. In this paper, our goal is tostudy the complex networks and various basic terms related tocomplex networks like mutual behavior between real-networksand complex networks, average path length, clusteringcoefficient, degree distribution. Designing and analyzing thebehavior and dynamics of a complex networked system are alsodiscussed. Hence, A complex networked system can helps usin: understanding the efficiency of new security approaches forcomputer networks, improving the design of computernetworks to make it more robust and resilience against errorsand failures occurred in system, understanding how populationwill respond to introduction of new nodes in system, detectingsubtle vulnerabilities, and also detecting catastrophic failures inpower grid.Networks define many structures or systems in nature. Thereare numerous examples of complex networks in real life or inscientific or computerized world; The Internet is a network ofmachines and routers, which are connected by physical linkssuch as optical fibers. Machines and routers in Internet acts asnodes and transmission media acts as links or edges as incomplex networks. Different websites in www constitutes anetwork. Neurons in brain constitute a network. People in anorganization constitute a network. Food webs, metabolicpathways, diseases and even viruses can also be represented bycomplex networks [1].General TermsUnderstanding the complex networks, Study of complexnetworksKeywordsComplex Networks, Understanding the complex networks,Complex networks in real life, Designing the networks.1. INTRODUCTIONComplex Networks are structures which are composed ofinteracting individual nodes abstracted from natural ortechnological systems. These nodes are connected by links oredges. Complex Networks have received great attention fromscientific communities in past decades and are currently beingstudied across many fields of science [1,2].Advancement in complex network have focused on networktopological characteristics and network dynamics [2]. ComplexFig. 1 – Network Structure of the InternetHowever, the goal of studying complex networks is not only toexamine the underlying structure of complex systems, but alsoto learn how we can control them more efficiently. A complexsystem is difficult due to the unknown architecture of thesystem [2]. According to control theory, a dynamic network iscontrollable if, for a selected choice of inputs, it can be derivedfrom any initial state to any desired final state within a finitetime [3].In late 1950s, two mathematicians, Erdos and Renyl described anetwork with complex topology by random graph [1]. Complexnetwork is the practical application of random graph. In arandom31
International Journal of Computer Applications (0975 – 8887)Volume 101– No.15, September 2014Fig. 2 - Representation of Cell as a Real-Life Complex Networkgraph, each vertex has random no. of vertices connected to it[4]. Their work had made a foundation of the random networktheory, and intense studies had been done in past 50-60 yearsand even today. Although, studies clearly shows that manyreal-life networks are neither regular nor completely random,but ER random graph model was the only sensible approachthat made scientists thinking about complex networks forabout half a century.Small-world effect and scale-free feature are the recentdiscoveries in complex networks [1].2. COMPLEX NETWORKS IN REALLIFECell is a network of genes and proteins which offers a feasiblestrategy for showing the complexity of living systems. Cellsand microorganisms have an impressive feature, which helpsthem to live in an environment. Even if any kind of changeoccur in environment, they can recover themselves accordingto that change. In addition to this, they have an amazingability to correct internal errors [5].According to basic principle of molecular biology, DNA is theultimate repository of biological complexity. It is generallyseen and accepted that information storage, informationprocessing and information execution of various cellularorganizations lies at different levels. These different levels ina cell are known as genes, mRNA, proteins and metabolites.However, the unconnected behavior of these organizationallevels has recently known. Usually, long-term information isstored in genes and proteins are used for short-terminformation storage [5].The bottom of the cell shows various molecular componentsof the cell which also acts as the functional organization in thecell. These molecular components are: genes, mRNA,proteins, metabolites. All these molecular componentstogether form the level 1 of pyramid. At level 2, thesemolecular components form regulatory motifs or metabolicpathways, which in collaboration form functional modules atlevel 3. At level 4, a scale-free hierarchical architecture isgenerated by combining these functional modules [5]. Thisproves universality of complex networks from a cell to theWorld Wide Web. Hence, complex networks can be extractedfrom real as well as technological systems [1].3. SOME BASIC CONCEPTS ABOUTCOMPLEX NETWORKAlthough many quantities and measures have been proposedabout complex networks in the last decades, but three basicconcepts defines the basic characteristics of complexnetworks. These basic concepts are: the average path length,clustering coefficient, and degree distribution. These conceptsare used to satisfy the small-world effect and scale-freefeature in complex networks. This section gives a brief reviewabout these concepts:32
International Journal of Computer Applications (0975 – 8887)Volume 101– No.15, September 2014Table 1– Table showing several networks; their size, clustering coefficient, average path length and degree exponentNetworkSizeClustering CoefficientAverage Path LengthDegree ExponentInternet, domain level327110.243.562.1Internet, router level2282980.039.512.1WWW1531270.113.1γin 2.1 γout Electronic Circuits3290.343.172.5Food Web1540.153.401.133.1 Average Path LengthIn a network, if two nodes labeled as i and j, then the distancedij between these nodes is defined as the number of edgesalong the shortest path connecting these two nodes. Thediameter D of a network, is hence defined as the maximumdistance among all the available distances between any pair ofnodes in the network [6]. Therefore, the average path length Lof a network is defined as mean distance between two nodes,averaged over all available paths between those nodes. Here,L defines the “Effective size of the network”. It has beendiscovered that average path length L of most complexnetworks whether they are natural or technological is small.This smallness defines small-world effect in complexnetworks [1].3.2 Clustering CoefficientIn a complex network, it is quite possible that neighbor of anode’s neighbor is also direct neighbor of a node, or inanother way two neighbors of a node are also neighbors ofeach other. This property is known as the “clustering of anetwork”. Clustering Coefficient C is defined as the averagepairs of neighbors of a node that are also neighbors of eachother [1]. Suppose that a node i in a network has q i edges, andthese qi edges connect this node to qi other nodes. All thesenodes are neighbors of node i. If every neighbor of node i isconnected to every other neighbor of node i, then atmostqi(qi-1)/2 edges can exist among them. Thus, the clusteringcoefficient Ci of node i is defined as, Ci 2Ei/( qi(qi-1)) ,where Ci is the ratio between Ei of edges that exist amongthese qi nodes and the total number of q i(qi-1)/2 edges. Hence,the clustering coefficient C of whole network is the average ofCi over all i. Thus, C 1; and C 1 iff the network is globallyconnected or coupled [7,20].3.3 Degree DistributionThe degree of each and every single node is the mostimportant characteristic in a network. The degree q i of a nodei is defined as the total number of its connections to othernodes. Thus, more the degree of a node, more important is thenode in a network. The average of ki over all number of nodesis the average degree of the network. The average degree of anetwork is denoted by k .A distribution function P(k) is defined as the probability that anode which is selected randomly has exactly k edges. Aregular lattice has a simple degree, because each node isconnected to equal no. of other nodes. So, a single sharp spikeis seen in the degree distribution graph. In a completelyrandom graph, the degree distribution sequence obeys thefamiliar Poisson distribution; and the shape of the Poissondistribution fall off rapidly, after reaching the peak value k .Because of this rapid fall, the probability of finding a nodewith k edges becomes negligibly small. In the past manyyears, many researchers have proved that the degreedistribution of the large-scale real networks, deviatesexceptionally from the Poisson distribution. The degreedistribution of a number of networks can be defined as thepower-law of the form P(k) k-γ, where γ is about 2[11,12,16,18].If the power-law distribution has the value of degree exponentunder 3, then a scale-free network continue to remainconnected indefinitely [11]. The power-law distribution fallsoff more slowly than Poisson distribution allowing for a fewnodes of very high degree to exist. Because these power-lawsare free of any scale; thus, such a network is called scale-freenetwork [1].Thus, many real-world or technological complex networkspossess small-world and scale-free features in common.4. DESIGNING OF COMPLEXNETWORKSMany real-world systems such as food-web, metabolicsystems and infrastructure systems such as road maps, circuitsystems can be analyzed and designed as complex networks.Optimization flows and designing a network are the twoclasses of problems which are focused by network designersand optimization researchers. The problem of optimizationflows in a network include finding the shortest path, minimumcost and maximum flow [8]. Optimization flow in a networkmeans there should be minimum number of nodes includedwhile transferring the data from sender to receiver in anetwork [10]. A network can be designed by using twoapproaches. These approaches are described below:4.1 Exogenous NetworkIn an exogenous network, a network designer has directcontrol over all the nodes and how these nodes are connectedto other nodes. In such kind of network, an external networkdesigner controls the various activities of a network; Hence, itis called the exogenously designed network [8].In an exogenously designed network, a node does not haveany information about its neighbors. All the controlinformation about a network, is kept by a network designer. A33
International Journal of Computer Applications (0975 – 8887)Volume 101– No.15, September 2014network designer uses such kind of information whiletransferring data from one node to another.Though an exogenous designed network is efficient andoptimal while performing a task; but they are slow, whichcauses congestion in a network. Hence, Such kind of approachis now getting obsolete [8].4.2 Endogenous NetworkIn an endogenous network, a network designer does notcontrol the nodes. However, decisions are made at local-levelby self-directed entities called nodes [8]. Local-level behaviorof these nodes affect the global structure of a network and itsproperties which in turn affects the overall performance of thenetwork. This approach of designing networks have gainedinterest in various research communities ranging from socialto economical to technical networks in last few years.5. ANALYSIS OF COMPLEXNETWORKED SYSTEMSConsider an example of the Internet as an endogenousnetwork where routers acts as nodes and physical transmissionmedia acts as communication links within these routers. Theserouters make optimal decisions about connecting to otherrouters while routing the data from one router to another.These local-level decisions made by routers affect the overallstructure of the Internet and therefore affecting theperformance of the Internet, which in turn providing morerobustness and more resilience in the Internet.5.1 Understanding Network StructureThis approach is a model of collaborative designing of anetwork where each node is capable of taking local-leveldecisions and hence contributing to the performance of thenetwork [10].Fig. 4 – A simple utility functionThe complex networked systems should be analyzed todevelop capabilities for understanding, designing and tocontrol these networked systems. For analyzing these systems,we should need to examine four major elements:understanding network structure; understanding networkdynamics; mathematical modeling and simulation; situationalawareness, design and control of complex networks. All thesefour elements are described below:The underlying topology of a network should be knownbeforehand to understand the network’s structure and itsbehavior. However, the network systems that are of interesthave very large scale and are complex too. The networkstructure of these systems cannot be concluded directly. So,statistical data and machine learning methods are used toconclude the network structure of these systems.The major problem is to conclude the network structure ofthese systems from the limited set of noisy observation. Theseobservations are not directly connected, though they may beindirectly connected. In many cases, these systems are of verylarge scale and may be spatially distributed [13].5.2 Understanding Network DynamicsFig. 3 – The relationship between node-level behavior,network structure, network properties and performanceof a networkChoosing a design for a network is a bit difficult process froma set of available designs. We can also modify the structuralfeatures of a complex network in such a way that it exhibitsthe desired dynamics [9]. A design should be chosen on thebasis of utilities provided by that particular design. So, wedefine a utility function for each design which represents theutilities for every point in a particular design. This utilityfunction is compared from design to design; Then, a design ischosen on the basis of maximum optimal value of utilityfunction [10].Thus, the goal of design process is to try finding a design withthe maximum optimal utility value, to obtain a ‘good enough’design [10,14].A networked system serves some dynamic processes that arethe principle objects of interest. Network’s Structure is theunderlying layer of Network’s dynamics and also providessome abstraction to the user. The objective of understandingthe network dynamics is to understand the network behavior –under a steady state or some varying state. In the steady state,behavior possessed by a network remains constant. But, invarying state, network’s behavior also varies [13].5.3 Mathematical Modeling and SimulationIf we have given mathematical or statistical model of acomplex network, we can study the model’s structure andproduce dynamic network’s behavior. Multiple levels ofexactness and accuracy are needed while modeling andsimulating a complex network. At the highest resolution level,simulations reproduce bits and instructions of the realcomplex dynamic networked system. At the lowest resolutionlevel, sophisticated mathematical models are required toabstract the crucial information about a network.Mathematical modeling of a complex network and simulatingits model’s structure helps in understanding the network’sbehavior and its dynamics.Performance optimization is done in large-scale simulations.Analysis of stability, errors and various convergenceproperties are also done in complex network simulations[13,17].34
International Journal of Computer Applications (0975 – 8887)Volume 101– No.15, September 20145.4 Situational Awareness, Design andControl of Complex NetworkThe fundamental goal of modeling and simulating a complexnetwork is to develop methods for understanding network’sbehavior, controlling various events and remove anomaliesfrom a complex networked system. The progress of a complexnetworked system depends on the study of these researchareas. The final step in analysis procedure of a complexsystem focuses on awareness or activeness, designing andcontrollability of a complex networked system.This step of analysis focuses on requirement of onlinelearning in complex networks and the control methods areused to modify behavior of a network. Awareness in acomplex network allows the network to change its dynamicsaccording to the situation, various design and control methodsare used to remove errors and optimization flow in a network[13,15,19].6. CONCLUSIONComplex Networks have received great attention in last fewdecades. Complex networks are the networks which can beseen in real-life or in technological systems. Complexnetworks have nodes and these nodes are connected by manylinks. They are called complex networks because thesenetworks have complex underlying architecture and complextopology which is difficult to understand. Complex Networkshave been discovered by two mathematicians Erdos and Renylin late 1950s. Life’s complexity pyramid satisfies the mutualbehavior of real-life networks with complex networks.Complex Networks share three basic concepts: average pathlength, clustering coefficient and degree distribution. Averagepath length defines the criteria for a network to have smallworld property. Clustering coefficient defines the coupling orconnectedness of network. It defines the average pairs ofneighbors of a node that are also neighbors of each other.These pairs in a network defines the clusters in a network.Degree distribution defines the criteria for a network to havescale-free property. Power-law degree distribution sequenceof a network allows few nodes to have high degree. Thesepower-laws are free from any scale. Therefore, complexnetworks satisfy the scale-free property.Design procedure of a network defines the criteria to design anetwork with maximum optimization achieved by a network.Network can be designed by two approaches: Exogenous andEndogenous approach. Utility function is used to calculate themaximum optimization achieved and maximum utilitiesprovided by the system.Analysis process studies the four main elements to developcapabilities, to understand the network’s behavior and itsdynamics. These four major elements are: understandingnetwork structure, understanding network dynamics,understanding network dynamics, mathematical modeling andsimulations, situational awareness, design and control ofcomplex networks. A proper analysis should be done tocontrol various events and remove anomalies from a complexnetworked system.7. ACKNOWLEDGEMENTS[2] Cun - Lai Pu, Wen-Jiang Pei, Andrew Michaelson,“Robustness analysis of network controllability”, inScience Direct, Elsevier, pp. 4420-4425,24 April 2012.[3] Yang - Yu Liu, Jean - Jacques Slotine and Albert –Laszlo Barabasi, “Controllability of Complex Networks”,in Nature, vol. 473, pp. 167-173, 12 May, 2011.[4] http://en.wikipedia.org/wiki/Random graph[5] Zoltan N. Oltvai and Albert – Laszlo Barabasi, “Life’scomplexity pyramid”, in Science, vol. 298, pp. 763-764,25 October, 2002.[6] Reka Albert, Hawoong Jeong and Albert – LaszloBarabasi, “Diameter of the world-wide web”, in Nature,vol.401, pp. 130-131, 9 September, 1999.[7] Matthieu Latapy and Clemence Magnien, “Measuringfundamental properties of real-world complex networks”,unpublished.[8] Zhenghui Sha and Jitesh H. Panchal, “Towards thedesign of complex evolving networks with highrobustness and resilience” in Science Direct, Elsevier,pp. 522-531, 2013.[9] Raoul – Martin Memmesheimer, Marc Timme,“Designing Complex Networks”, in Science Direct,Elsevier, pp. 182-201, 3 November, 2006.[10] Mark Klein, Hiroki Sayama, Peyman Faratin, YaneerBar-Yam, “What complex systems research can teach usabout collaborative system”, unpublished.[11] Albert – Laszlo Barabasi, “Network Science”, Phil.Transactions of Royal Society A, vol. 371, 18 February,2013.[12] Albert – Laszlo Barabasi, “Scale-free Networks: Adecade and beyond”, in Science, vol. 325, pp. 412-413,24 July, 2009.[13] James M. Brase, David L. Brown, “Modeling,Simulation and analysis of complex networked systems”,in May 2009.[14] Ana Pinto, “Designing and the functioning of aproductive learning network”, in 9th InternationalConference on Productive Learning, 2014.[15] A. Clauset, H.G. Tanner, C.T. Abdallah, R.H. Byrne,“Controlling across complex networks: emerging linksbetween network and control”, submitted to Elsevier.[16] I. Farkas et. al., “Networks in life: scaling properties”, inScience Direct, Elsevier, vol. 314, pp. 25-34, 2002.[17] Marta C. Gonzales and Albert – Laszlo Barabasi, “Complex Networks: from data to models”, in NaturePhysics, vol. 3, pp. 224-225, April 2007.[18] Reka Albert, Hawoong Jeong and Albert – LaszloBarabasi, “Error and attack tolerance of complexnetworks”, in nature, vol. 406, pp. 378-381, 27 July,2000.8. REFERENCES[19] Tao Jia and Albert- Laszlo Barabasi, “Control capacityand a random sampling method in exploringcontrollability of complex networks, in ScientificReports, 5 August, 2013.[1] Xiao Fan Wang and Guanrong Chen, “ComplexNetworks: small-world, scale-free and beyond”, in IEEECircuits and Systems Magazine, First Quarter, 2003.[20] Matthieu Latapy and Clemence Magnien, “ComplexNetwork Measurements: Estimating the relevance ofobserved properties”, unpublished.We want to thank Dr. Sandeep Sood for their guidancetowards the work.IJCATM : www.ijcaonline.org35
study the complex networks and various basic terms related to complex networks like mutual behavior between real-networks and complex networks, average path length, clustering . approaches. These approaches are described below: 4.1 Exogenous Network In an exogenous network, a network designer has direct .
neural networks using genetic algorithms" has explained that multilayered feedforward neural networks posses a number of properties which make them particularly suited to complex pattern classification problem. Along with they also explained the concept of genetics and neural networks. (D. Arjona, 1996) in "Hybrid artificial neural
Trend Analysis of E-Commerce Data using Hadoop Ecosystem - ijcaonline.org . ijca
1 EOC Review Unit EOC Review Unit Table of Contents LEFT RIGHT Table of Contents 1 REVIEW Intro 2 REVIEW Intro 3 REVIEW Success Starters 4 REVIEW Success Starters 5 REVIEW Success Starters 6 REVIEW Outline 7 REVIEW Outline 8 REVIEW Outline 9 Step 3: Vocab 10 Step 4: Branch Breakdown 11 Step 6 Choice 12 Step 5: Checks and Balances 13 Step 8: Vocab 14 Step 7: Constitution 15
8 ECDHLP_v2_2101_1 b-2 oral tablet50 mg 1 b-50 1 MO b-50 complex oral tablet extended release 1 b-6 oral tablet100 mg 1 MO b-caro-t 1 b-compleet-100 1 MO b-compleet-50 1 MO b-complex balanced 1 MO B-COMPLEX INJECTION 2 b-complex oral tablet 1 MO b-complex-c oral tablet 1 MO b-complex/b-12 oral 1 MO b-complex/vitamin c 1 MO
Complex Analysis in the near future. (In Complex Analysis) We study the behavior of differentiable complex-valued functions f(z) of a complex variable z. The key idea in an introductory course is that complex differentiability is a much more restrictive condition than real differentiability. In fact, complex-differentiable functions are so
1 COMPLEX ALGEBRA AND THE COMPLEX PLANE 4 A B C Triangle inequality: jABj jBCj jACj For complex numbers the triangle inequality translates to a statement about complex mag-nitudes. Precisely: for complex numbers z 1, z 2 jz 1j jz 2j jz 1 z 2j with equality only if one of them is 0
Complex Products under GDUFA II Complex active ingredients - E.g., Complex mixtures of APIs, polymeric compounds, peptides Complex formulations - E.g., Liposomes, suspensions, emulsions, gels Complex routes of delivery - E.g., Locally acting such as ophthalmic, otic, dermatological and inhalational drugs Complex dosage forms
S1 Akuntansi Pendidikan Profesi: PPAk S2 Magister Science, Magister Terapan S3 Ilmu Akuntansi Pendidikan IAI: KAPd. dan KASP Asosiasi Profesi Akuntansi: IAPI dan IAMI Asosiasi Profesi lain terkait akuntansi dan Internasional –Internal Auditor, CISA, ACCA, CMA, CIMA, CPA Negara lain Asosiasi Profesi PPAJP Kemenkeu Kemendiknas - DIKTI BNSP OJK Internasional .
